📕문제

[Baekjoon] 18222. 투에-모스 문자열

문제 설명

0과 1로 이루어진 무한한 문자열 X가 존재할 때 k번째에 무슨 문자가 오는지 구하는 문제다.
문자열 X는 다음과 같은 규칙으로 이루어진다.

1. X는 맨 처음에 "0"으로 시작한다.
2. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다.
3. X의 뒤에 X'를 붙인 문자열을 X로 다시 정의한다.
4. 2~3의 과정을 무한히 반복한다.

즉 처음에는 "0",
이후 "0"을 뒤바꾼 문자열 "1"을 뒤에 붙여 "01",
"01"을 뒤바꾼 문자열 "10"을 뒤에 붙여 "0110",
"0110"을 뒤바꾼 문자열 "1001"을 뒤에 붙여 "01101001",
계속 반복해 "011010011001011010010110011010011001011001101001⋯⋯"이 된다.

📝풀이

위 규칙에 따라 X를 구해보면 "0" -> "01" -> "0110" -> "01101001" ...
길이가 2배씩 늘어나는 것을 알 수 있다.

이를 역으로 생각해 X의 길이를 2의 거듭제곱만큼 줄여서 처음 문자열인 "0"으로 되돌아간다고 생각해보자.

먼저 k보다 작고 가장 가까운 2의 거듭제곱을 구하고 뺀다.
즉, k번째 문자를 찾는 대신 $k-2^n$번째 문자를 찾으면 된다.

이때 k번째 문자는 $k-2^n$번째 문자를 뒤집은 것이므로
k번째 문자 = 1 - ($k-2^n$ 번째 문자) 가 된다.

이 과정을 반복해 첫번째 문자까지 뒤집게 되면 k번째 수가 "0"에서 어떻게 변했는지 알 수 있다.

정리하자면

1. k에서 k와 가장 가깝고 작은 2의 거듭제곱을 뺀다.
2. 1.이 이루어질 때마다 문자를 반전시킨다.
3. k가 1이 될 때 까지 1., 2.를 반복한다.

코드로 구현하면

import sys

read = sys.stdin.readline

k = int(read())


def thue_mose(k):
    if k == 0:
        return 0
    else:
        x = 1
        while x * 2 <= k:
            x *= 2
        return 1 - thue_mose(k - x)


print(thue_mose(k - 1))

분할정복 문제라 일단 분할정복으로 풀었지만 문제를 푸는 과정에서 하나의 규칙을 발견했다.

해당 풀이는 2의 거듭제곱만큼 뺄때마다 "0"에서 반전이 된다.
그렇다면 k가 몇개의 2의 거듭제곱의 합으로 이루어졌는지만 구하면 된다.

즉, 2진수로 바꿨을 때 1의 개수를 구하는 문제다.
1의 개수가 짝수면 "0"그대로, 홀수면 반전된 "1"이 된다.

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

코드 한줄이면 풀 수 있다.