[Python/파이썬] 백준 18222번 투에-모스 문자열

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())
ans = 0
length = 1

def make_arr(k):
    global ans, length
    if length >= k:
        return
    ans = (ans << length) | (ans ^ (2**length-1))
    length *= 2
    make_arr(k)
    
make_arr(k)
print(ans & (1 << (length-k)))

• Python3로는 시간 초과, PyPy3로는 메모리 초과...
• 비트연산을 이용하여 풀이하면 빠르게 될 줄 알았는데 k의 범위가 워낙 커서 안되는것 같다.

 

 

투에-모스 점화식 이용

k = int(input())

def func(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    elif num % 2 == 0:
        return func(num//2)
    else:
        return 1 - func(num//2)
    
print(func(k-1))

투에-모스 수열을 구하는 점화식이 있었다. 이 점화식을 이용하면 쉽게 분할정복으로 풀이할 수 있었다.

투에-모스 수열 점화식

 

투에-모스 수열 - 위키백과, 우리 모두의 백과사전