18222 - 메모리 초과 - 해답

투에-모스 문자열

 

문제

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

 

X는 맨 처음에 "0"으로 시작한다. 

X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다.

X의 뒤에 X'를 붙인 문자열을 X로 다시 정의한다. 

2~3의 과정을 무한히 반복한다.

즉, X는 처음에 "0"으로 시작하여 "01"이 되고, "0110"이 되고, "01101001"이 되고, ⋯ 

의 과정을 거쳐 다음과 같이 나타내어진다.

 

    "011010011001011010010110011010011001011001101001⋯⋯"

 

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

 

입력

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

 

출력

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

---

뭔가 쉽다고 생각했는데 메모리가 문제... 이 문제를 어떻게 해결해야할까?

import sys

k = int(sys.stdin.readline())

tm_st = "0"

while(len(tm_st) < k):
    co_st = tm_st
    co_st = co_st.replace("1","2")
    co_st = co_st.replace("0","1")
    co_st = co_st.replace("2","0")
    tm_st += co_st
    
print(tm_st[k-1])

재귀로 풀어야한다고해서 재귀식을 생각해 보았으나 생각이 나지않아 찾아 보았다.

그래서 찾은 식이 

t0 = 0
t2n = tn
t2n+1 = 1 - tn

import sys

N = int(sys.stdin.readline())

# 재귀식 사용
# t0 = 0
# t2n = tn
# t2n+1 = 1 - tn
def sol(N):
    if N == 0:
        return 0
    elif N % 2:
        return 1 - sol(N//2)
    else:
        return sol(N//2)

# 시작이 0이라서 1을 빼고
print(sol(N - 1))