[백준 18222번] 파이썬 - 투에-모스 문자열

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

시간 제한 1초, 메모리 제한 256MB

# 조건

• 0과 1로 이루어진 길이가 무한한 문자열 X가 있다.
• 이 문자열은 다음과 같은 과정으로 만들어진다.
  1. X는 맨 처음에 "0"으로 시작한다.
  2. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 _X'_을 만든다.
  3. X의 뒤에 _X'_를 붙인 문자열을 X로 다시 정의한다.
  4. 2~3의 과정을 무한히 반복한다.
• 즉, X는 처음에 "0"으로 시작하여 "01"이 되고, "0110"이 되고, "01101001"이 되고, ⋯ 의 과정을 거쳐 다음과 같이 나타내어진다.
  • "011010011001011010010110011010011001011001101001⋯⋯"
• 자연수 k가 주어졌을 때 X의 k번째에는 무슨 문자가 오는지 구하여라.

입력

• 첫 번째 줄에 자연수 k (1 ≤ k ≤ 10^18) 가 주어진다.

출력

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

# 접근 방법

• 우선 확인해야되는 k의 범위가 상당히 크므로 분할정복을 이용하여 풀어주어야 시간 초과가 나지 않을 것이다.
• 투에모스 문자열을 10개정도 나열하면 0 1 1 0 1 0 0 1 1 0 과 같이 생성된다.
• 이 때 제일 처음오는 0을 0번째 인덱스로 놔두고 규칙을 찾아보자.
  • 1번째 인덱스의 수 1은 1 // 2 의 수인 0의 반대인 1
  • 2번째 인덱스의 수 1은 2 // 2 의 수인 1과 같은 1
  • 3번째 인덱스의 수 0은 3 // 2 의 수인 1의 반대인 1
  • 즉 홀수번째 오는 수는 // 2를 했을 때의 수와 반대이고
  • 짝수번째 오는 수는 // 2를 했을 때의 수와 같다.
• divide_conquer 함수의 인자로는 현재 확인하는 자리의 수를 넘겨준다.
  • 내부의 로직은 0인 경우 0을 리턴
  • % 2 가 존재하는 경우 => 홀수인 경우 not divide_conquer(idx // 2)
  • 짝수인 경우 => divide_conquer(idx // 2)

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

def divide_conquer(idx):  
    if idx == 0:  
        return False  
    if idx % 2:  
        return not divide_conquer(idx // 2)  
    else:  
        return divide_conquer(idx // 2)  
K = int(input())  
print(1 if divide_conquer(K-1) else 0)