mingssssss

1. 문제

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 ≤ 10^18) 가 주어진다.

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

예제 입력 1
1
예제 출력 1
0
예제 입력 2
2
예제 출력 2
1
예제 입력 3
10
예제 출력 3
0

2. 코드

k = int(input()) # 입력값
n  = 0 # 2^n을 구할 변수
cnt = 0 # 연산이 몇 번 이루어 졌는지 확인하는 변수

while k > 2: # 0과 1만 구하면 되므로,
    if k > 2**n:
        n += 1
    else:
        n -= 1 # n값 그대로 사용하면 음수가 나온다.
        k = k - (2**n)
        n = 0
        cnt += 1
if k == 1:
    if cnt % 2 == 0:
        print('0')
    else:
        print('1')
elif k == 2 or k == 0:
    if cnt % 2 == 0:
        print('1')
    else:
        print('0')

3. 리뷰

처음에 보고 문제 그대로 코드를 짜면 쉽게 풀 거 같았지만... 일단 입력이 10^18까지 큰 숫자가 들어오고 while문과 for문으로 큰 숫자를 돌리려고 하니 당연히 메모리 초과가 났다.
숫자를 직접 잇는 방식으로는 처리가 불가능 할 것 같아서 k를 줄이는 방법을 생각해보았다.
20까지의 숫자를 직접 써봤더니 k에서 2^n을 반복적으로 빼면 결국 첫 번째 혹은 두 번째 숫자로 귀결된다는 것을 알았다. 해당 로직을 이용해 결국 첫 번째 숫자인지, 두 번째 숫자인지 확인한 후, k에서 2^n을 뺀 cnt를 따로 세서 cnt가 짝수이면 원래 숫자이므로 그 숫자 그대로를, 홀수이면 그 숫자의 반대 숫자를 출력하게 했다. 이번 문제로 입력값을 잘 보고 효과적으로 연산을 줄이는 방법을 잘 생각해야겠다고 다짐했다.
다른 풀이를 보니 점화식을 사용했다. 점화식이 익숙하지 않지만 익숙해지려고 노력해야겠다.

k = int(input())
def recursive(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n%2:
        return 1-recursive(n//2)
    else:
        return recursive(n//2)
print(recursive(k-1))

*참고(1줄 짜리 괴물 코드)

print(bin(int(input())-1).count('1')%2)