[백준] 18222번 투에-모스 문자열 ( Java )

문제 (Silver 2)

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

18222번: 투에-모스 문자열

---

풀이

접근

설명

1과 0을 1과 -1이라고 생각하자! ( 부호의 차이로 생각하자! )

2의 제곱 수(2,4,8,16,...)만큼 앞뒤로 대칭되고 있는 문자열! 

즉, N보다 작은 2의 제곱수를 뺀 인덱스 값(N - (2*?)) 을 알면 N의 값을 알게 됨

위의 예시로 설명하자면, 27번째 값은 11번째 값과 같음(부호만 반대)

11번째 값은 3번째 값과 같음 ... 이 반복됨 => 재귀!

 

즉, N보다 작은 2의 제곱수를 뺀 인덱스 값을 찾으며 재귀를 타고 1이 됐을 때에 0을 리턴해준다. 

이때 한번 재귀를 돌때마다 0은 1로, 1은 0으로 변환해야하기 때문에, 1에서 리턴받은 값을 빼주어 간단하게 구해준다!

코드

import java.util.*;
import java.io.*;

public class Main{
    static int res = 0;
    static long[] pow;	// 2의 제곱수들을 저장해 놓는 배열
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());

        pow = new long[64];

        pow[0] = 1;
        for(int i = 1 ; i < 64 ; i++){
            pow[i] = pow[i-1]*2;
        }

        System.out.println(toemos(n));
    }

    private static int toemos(long n) {
        if(n == 1){
            return 0;
        }
        for(int i =0 ; i < 64 ; i++){
            if(pow[i] >= n) return 1 - toemos(n - pow[i-1]);
        }
        return 0;
    }

}