SWEA[7584] - 자가 복제 문자열

링크

SWEA[7584]

문제설명

• 규칙찾기

문제풀이

1:    -    -    3    -
0:    1    2    -    4    

에서

1:    7    6    3
0:    1    2    5    4    

이렇게 2^n 기준으로 빈칸 채우기

2^n-K 값은 K에서 값이 바뀜.
K=2^n 이면 무조건 0으로 쭉 감
이렇게 반복하면 0 또는 1로 남음.
값이 바뀌는 횟수를 계산하면 됨

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution7584 {

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/swea/7584.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            long K = Long.parseLong(br.readLine());
            long temp = 2;
            int cnt=0;
            while(K>2) {
                temp=2;
                while(temp<K) {
                    temp *=2;
                }
                if(temp==K) {
                    break;
                }
                K=temp-K;
//                System.out.println(K);
                cnt++;
            }
//            System.out.println("cnt: "+cnt);
            int ans= cnt%2;
            System.out.println("#"+test_case+" "+ans);
            /*
             * 초기화
             */
        }//end test_case
    }//end main
}

아쉬운점

• 문제 제대로 안읽어서 스트링 만드는 것으로 알았음
• 규칙 잘못보고 수열 잘못만들었었음
• K = 2^n 일 때 무한루프 걸렸음
• 더 쉬운 규칙
  • 001/-/011/- 반복

잘한점

• 규칙찾음