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

 

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

18222번: 투에-모스 문자열

문제

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 ≤ 1018) 가 주어진다.

출력

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

 

import java.io.*;

public class Main {
    static long[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long N = Long.parseLong(br.readLine());

        arr = new long[64];
        arr[0] = 1;
        for (int i = 1; i < 64; i++){
            arr[i] = arr[i-1] * 2;
        }
        System.out.println(sol(N));
    }
    public static int sol(long x){
        if (x == 1) return 0;
        for (int i = 0; i < 64; i++){
            if (arr[i] >= x) return 1 - sol(x - arr[i-1]);
        }
        return 0;
    }
}

1. 어려웠던 점:

- 재귀가 아직 어색하다.

 

2. 알게된 점:

- 재귀를 사용한 분할정복

 

3. 알고리즘 풀이:

- 문자열은 2의 배수로 증가한다.

문자열을 도표로 그려보면, n의 값은 n보다 작은 2의 거듭제곱을 뺀 숫자에 해당하는 값을 반전한 값임을 알 수 있다.

0이면 1, 1이면 0으로 반전되기 때문에 1 - X 꼴로 return 해준다.

초기 숫자 1은 0