[백준 18222] 투에-모스 문자열

투에-모스 문자열(18222)

문제 출처 : https://www.acmicpc.net/problem/18222

 

k를 입력 받아 그 값이 0인지, 1인지를 찾는 문제 입니다. 재귀로 풀 수 있는 문제로 재귀를 이제 막 배웠다면 조금 어려울 수 있습니다.

문제 이해하기

문자열 x는 10 ** 18 이라는 엄청난 크기를 가지고 있습니다. 따라서 하나 하나 계산 해서는 답을 구할 수 없습니다. 문자열 x는 두 배씩 커지면서 매 번 값이 반전된다는 것을 이용하면 문제를 좀 더 쉽게 해결 할 수 있습니다.

문제를 이해하기 위해 x를 만들어 보겠습니다. 처음 x는 0 입니다.

0

이제 x를 반전해서 이어 붙여 줍니다.

0 1

다음 역시 x를 반전해서 이어 붙여 줍니다.

0 1 1 0

이것의 길이를 두 배씩 늘려주면 다음과 같습니다

0 1 1 0 1 0 0 1

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

0부터 시작해서 두 배씩 늘어나고, 각 값은 반전된다는 것만 기억하면 됩니다.

코드 작성하기

그럼 코드를 작성해 보겠습니다.

입력 받기

k = int(input())

문자열 X의 k번째 수를 찾기 위한 k를 입력 받습니다.

재귀 함수 구현

def solve(k):
    if k == 1:
        return False
    
    x = 1
    while x + x < k:
        x += x

    return not solve(k - x)

k 가 1일 때 0입니다. 반전을 시키기 위해 0을 False로 리턴합니다. x의 길이는 매 번 두 배씩 늘어납니다. 따라서 x의 길이가 k보다 커지지 않는 범위까지 x의 길이를 늘려줍니다. 그리고 k에서 계산한 x의 길이를 빼줍니다. 그럼 k 에서 x를 빼준 만큼 반전된 X를 가지게 됩니다. 이것을 재귀로 k값이 1이 될때까지 진행하면 문제에서 주어진 k값이 True인지, False인지 알 수 있습니다.

출력하기

print(1 if solve(k) else 0)

최종적으로 solve 함수의 값이 True가 되면 1을 출력하고, False이면 0을 출력하면 원하는 k값을 얻을 수 있습니다.

전체 코드

전체 코드를 확인해 보겠습니다.

def solve(k):
    if k == 1:
        return False
    
    i = 1
    while i + i < k:
        i += i

    return not solve(k - i)

k = int(input())
print(1 if solve(k) else 0)