[Algorithm] BaekJoon : 18222. 투에-모스 문자열 by Python

[문제 바로가기]

18222번: 투에-모스 문자열

📌문제 설명

0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다.

1. X는 맨 처음에 "0"으로 시작한다.
2. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다.
3. X의 뒤에 X'를 붙인 문자열을 X로 다시 정의한다.
4. 2~3의 과정을 무한히 반복한다.

즉, X는 처음에 "0"으로 시작하여 "01"이 되고, "0110"이 되고, "01101001"이 되고, ⋯ 의 과정을 거쳐 다음과 같이 나타내어진다.

"011010011001011010010110011010011001011001101001⋯⋯"
자연수 k가 주어졌을 때 X의 k번째에는 무슨 문자가 오는지 구하여라.

 

입력

첫 번째 줄에 자연수 k (1 ≤ k ≤ 1018) 가 주어진다.

 

출력

첫 번째 줄에 k번째에 오는 문자를 출력하라.

---

💡 문제 풀이

처음에 문제에 주어진 그대로 러프하게 코드를 구현했더니 당연히(?) '시간초과'가 발생하였다.

쉽게 규칙을 찾지 못해서 검색을 통해 점화식을 알아냈고

 

위와 같은 점화식을 가지는 수열임을 확인하여 재귀를 이용해 코드를 작성했다.

k = int(input())
def recursive(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n%2:
        return 1-recursive(n//2)
    else:
        return recursive(n//2)
print(recursive(k-1))

---

※ 다른 사람의 풀이

print(bin(int(input())-1).count('1')%2)

이건... 공부 좀 해봐야겠다 😂

---