[백준] #18222 Python

백준 18222번 파이썬
https://www.acmicpc.net/problem/18222

아이디어

2의 제곱수의 범위 별로 0에서 1로, 1에서 0으로 바뀌기 때문에 주어진 수가 2의 제곱수의 어떤 범위 내에 있는지 파악한다 + 재귀함수를 통해서 왼쪽 범위의 값과의 차이가 1과 0이 될 때까지 좁혀나간다.

차이가 0일 때 = 한 제곱 범위의 끝 -> 2의 제곱수 번째는 0부터 시작해서 0과 1을 반복해서 나아가기 때문에 재귀를 짝/홀번 돌렸는지에 따라 값이 결정된다.

차이가 1일 때 = 한 제곱 범위의 시작 -> 2의 제곱의 범위를 하나씩 좁혀 나갈 때, 좁혀 나간 범위내의 구한 값에서 0이면 1로, 1이면 0으로 바꿔줘야 한다. 따라서 재귀를 짝/홀뻔 돌렸는지에 따라 값이 결정된다.

전체코드

import sys
input = sys.stdin.readline


def SQ(n, rec):
    s = 0
    while True:
        if 2**(s) >= n:
            break
        s +=1
    
    ran = 2**(s-1)
    if n-ran == 0:
        if rec % 2 == 0:
            return 0
        else:
            return 1
    elif n-ran == 1:
        if rec % 2 == 0:
            return 1
        else:
            return 0
    else:
        return SQ(n-ran, rec+1)


k = int(input())
if k == 1:
    ans = 0
else:
    ans = SQ(k, 0)

print(ans)

느낀점

처음엔 완벽하게 이해했다기보디는 이렇게 하면 될 것 같다는 추측에 의해서 풀었었는데, 블로그로 정리를 해보니 이해할 수 있었다.
재귀함수 -> 해야할 행동을 스택으로 쌓아놓는 식으로 이해!