[BOJ] [Python] 18222 : 투에-모스 문자열

X는 0을 시작으로 X  +=  X'을 반복한다. 

 

 

시간초과 때문에, 점화식을 찾아서 풀어야 하는 문제이다.

헤매다가 결국 위키백과를 참고해서 풀었다.

 

점회식은 아래와 같다.

 

T(0) = 0

T(2n) = T(n)

T(2n + 1) = 1 - T(n)

 

수기

 

n을 0부터 시작하는 것으로 봤기 때문에, k -= 1 해서 생각한다.

 

예를 들어보자,

 

K = 6

n = 5 -> n = 2 -> n = 1

return 1 -> return 1 -> return ( 1 - 1 )

 

K = 5

n = 4 -> n = 2 -> n = 1

return 1 -> reutrn 1 -> return 1

 

 

# t(0) = 0
# t(2n) = t(n)
# t(2n + 1) = 1 - t(n)

k = int(input())


def find(x):
    if x == 0:
        return 0

    elif x == 1:
        return 1

    elif x % 2 == 0:
        return find(x // 2)

    else:
        return 1 - find(x // 2)


print(find(k - 1))