[JAVA] [SWEA] 7584. 자가 복제 문자열

문자열 P는 스스로를 계속 복제해서 매우 긴 문자열이 되었다.

복제하는 방법은 다음과 같다.

P0 = “0”

Pi+1 = Pi + “0” + f(g(Pi))

여기서, f(A) 함수는 문자열 A의 모든 문자를 반전시킨다.

예를 들어서, f(“10110”) = “01001”이다.

g(A)함수는 문자열 A를 좌우 반전 시킨다. 예를 들어서, g(“10110”) = “01101” 이다.

위와 같은 복제 방법을 무한히 반복한 문자열 P의 K번째 문자가 무엇인지 구하여라.

 

P1 = “001”

P2­ = “0010011”

P3 = “001001100011011”

위와 같이 복제가 이루어질 것이다.

따라서 3번째 문자는 1, 7번째 문자는 1, 10번째 문자는 0이다.

 

이 문제는 문자들의 규칙을 보고 점화식만 세워서 바로 추정하면 풀리는 문제인데

 

나도 처음에는 도대체 규칙이 무엇인지 한참을 쳐다보다가 알게 되었다.

 

인덱스를 문제처럼 맨 처음의 숫자를 첫번째로 하는 것이 아니라 0 번째라고 하였을때

 

1. 4의 배수의 숫자는 0 이다. f( 4n ) = 0

2. 4의 배수가 아닌 짝수는 1 이다. f( 4n + 2 ) = 1

3. 홀수의 경우 f( 2n + 1 ) = f( n )

 

이 규칙을 통해서 간단하게 코드를 짤 수가 있다.

 

1. 먼저 홀수 짝수를 나누고

2. 홀수 일 경우 1을 빼고 2를 나누어 준다.

3. 이 수가 4로 나누어 나머지가 0인지 확인한다.

4. 아니라면 2로 나누어 나머지가 0인지 확인한다.

5. 2~4 번을 반복하여 몇번째 숫자가 무엇인지 확인한다.

 

이때 0일 경우 0, 1일 경우 0 이기 때문에 초기 result 값은 0으로 해준다.

 

코드로 나타내면 다음과 같다.

 

이 문제의 경우 입력받는 k의 수가 10^18 까지 이기때문에 long으로 처리하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class D3Solution7584 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		long k = 0;
		int result = 0;
		for(int t=1; t<=T; t++) {
			k = Long.parseLong(br.readLine())-1;
			result = 0;
			while(k > 0) {
				if(k%2 == 1) k = (k-1)/2;
				if(k%4 == 0) {result = 0; break;}
				else if(k%2 == 0) {result = 1; break;}
			}
			bw.write("#"+t+" "+result+"\n");
		}
		br.close();
		bw.close();
	}

}