18222. 투에-모스 문자열

문제

백준 18222번 투에-모스 문자열

---

풀이

처음에 당연히 틀릴거 알지만 무지성으로 while문써서 한번 채점 돌리고 메모리초과 맞았다 ㅎ

k = int(input())
x = '01'
while len(x) < k:
    x += x[len(x)//2:] + x[:len(x)//2]
print(x[k-1])

근데 한참 생각해도 도저히 모르겠어서 검색해보고.. 투에모스 수열이라는 걸 처음 알게되었음ㅎ;;ㅎㅎ;

다음과 같은 점화식을 가진다고 한다.

점화식대로 재귀함수 뚝딱해줬다.

def t(n):
    if n == 0: return 0
    elif n == 1: return 1
    if n % 2: return 1 - t(n//2)
    else: return t(n//2)

k = int(input()) - 1
print(t(k))