[BOJ]18222号トエモス文字列(Java)

質問する

18222番:ダブルエモス文字列

に答える

に近づく

説明:

1と0を1と-1に考えましょう!△記号の違いだと思ってください.
2の平方数(2、4、8、16...)前後対称の文字列! 
すなわち,インデックス値からNより小さい2の平方数(n−(2*?)を減算する.知っていればNの値がわかる
上記の例では、27番目の値は11番目の値(コードとは逆)に等しい
11番目の値は3番目の値に等しい...繰り返し=>戻る!
すなわち,Nより小さい2の平方数を減算したインデックス値を求め,1に戻ると0を返す. 
このとき,1回返すごとに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;
    }

}