[Python] 백준 18222 - 투에-모스 문자열 문제 풀이

Overview

BOJ 18222번 투에-모스 문자열 Python 문제 풀이
분류: Divide and conquer (분할정복)

문제 페이지

https://www.acmicpc.net/problem/18222

풀이 코드 1

from sys import stdin
from math import log


def thue_morse(idx: int) -> int:
    if idx == 0:
        return 0

    x = int(log(idx, 2))

    val = 0
    while x > 0:
        if idx >= 2 ** x:
            val ^= 1
            idx %= 2 ** x
        x -= 1

    return [val, val ^ 1][idx == 1]


def main():
    k = int(stdin.readline())
    print(thue_morse(k - 1))


if __name__ == "__main__":
    main()

투에-모스 문자열의 길이는 2 ^ i로 나타낼 수 이다. 인덱스 k - 1을 포함한 투에-모스 문자열의 길이 i에서 1을 뺀 x를 구한다. 그 다음 반복문을 통해 이전 투에-모스 문자열의 k 값을 구해간다.

풀이 코드 2 - 점화식 이용

from sys import stdin


def thue_morse(idx: int) -> int:
    if idx == 0:
        return 0
    elif idx == 1:
        return 1
    elif idx % 2 == 0:
    	return thue_morse(idx // 2)
    else:
        return 1 - thue_morse(idx // 2)


def main():
    k = int(stdin.readline())
    print(thue_morse(k - 1))


if __name__ == "__main__":
    main()

위키피디아의 투에-모스 수열(https://ko.wikipedia.org/wiki/%ED%88%AC%EC%97%90-%EB%AA%A8%EC%8A%A4_%EC%88%98%EC%97%B4) 항목에 따르면 다음과 같이 점화식을 나타낼 수 있다.

따라서 위 코드와 같이 재귀적으로 풀이할 수 있다.

이미지 출처: "투에-모스 수열," ko.wikipedia, last modified MAR 09, 2022, accessed MAR 16, 2022, https://ko.wikipedia.org/wiki/%ED%88%AC%EC%97%90-%EB%AA%A8%EC%8A%A4_%EC%88%98%EC%97%B4