[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번째 문자가 무엇인지 구하여라.

 

풀이방법

주어진 시간은 2초, 입력이 최대 10^18이므로 반복문, 재귀를 사용할 생각을 일찍이 버린다.

 

주어진 문제를 해결할 수 있는 규칙을 찾는다.

 

P1 = “001”

P2­ = “0010011”

P3 = “001001100011011”

 

문제에 주어진 예시를 보면서, 자가분열이 몇 번을 진행되던 k번째의 값은 같은 것을 알 수 있다.

 

그렇다면, k번째 숫자가 0인지 1인지 판별할 수 있는 규칙을 찾아야한다.

 

P3에서

 

i    0   1   2   3   4   5   6   7   8    9    10   11   12   13   14

v   0  0   1   0   0   1   1    0   0    0     1     1     0   1     1

 

1 이 되는 인덱스 :  2, 5, 6, 10, 11, 13, 14

0 이 되는 인덱스 : 0, 1, 3, 4, 7, 8, 9, 12

 

0이 되는 i는 4의 배수가 있고, 1이되는 i는 4의 배수가 아니면서 2의 배수가 있는 것을 확인할 수 있다.

 

홀수의 경우 짝수가 될 때까지, i-1/2의 과정을 반복하고 짝수가 되었을 때, 위의 규칙을 적용시키면 된다.

 

즉,

 

i가 홀수 이면, 짝수가 될 때까지 (i-1)/2를 반복

 

i가 짝수 이면서 i가 4의 배수일 경우 : 1

 

i가 짝수 이면서 i가 4의 배수가 아닌 2의 배수일 경우 : 0

 

소스코드

package samsung;

import java.util.*;

public class s_7584 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			Long k = sc.nextLong() - 1;
			int n = 0;
			while(k >= 0) {
				if(k % 2 == 1) 
					k = (k - 1)/2;
				if(k % 4 == 0) {
					n = 0;
					break;
				}
				else if(k % 2 == 0) {
					n = 1;
					break;
				}
			}
			System.out.println("#" + t + " " + n);
		}
	}
}