이 문제의 경우 투에-모스 문자열의 점화식을 찾아보고 점화식을 이용하여 쉽게 구현하였다. 투에-모스 문자열의 점화식은 다음과 같다.

n을 계속 2로 나눠주며 n이 0이나 1이 되었을 경우에 값을 반환하고 그 외에는 짝수 홀수 여부를 판단하며 n을 갱신해나간다. 이를 코드로 작성하면 다음과 같이 작성할 수 있다.

• recursion함수를 n을 인자로 갖도록 하여 선언한다.
  -> 만약 n이 0일 경우 0을 반환한다.
  -> 만약 n이 1일 경우 1을 반환한다.
  -> 만약 n이 홀수일 경우, 1-recursion(n//2)을 재귀호출한다.
  -> 만약 n이 짝수일 경우, recursion(n//2)를 재귀호출한다.
• k를 입력받는다.
• recursion(k-1)을 출력한다.

Code

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