[SWEA] - 7584. 자가 복제 문자열 (D3)

[문제]

문자열 P는 스스로를 계속 복제해서 매우 긴 문자열이 되었다.
복제하는 방법은 다음과 같다.
P0 = “0”
Pi+1 = Pi + “0” + f(g(Pi))
여기서, f(A) 함수는 문자열 A의 모든 문자를 반전시킨다.
예를 들어서, f(“10110”) = “01001”이다.
g(A)함수는 문자열 A를 좌우 반전 시킨다. 예를 들어서, g(“10110”) = “01101” 이다.
위와 같은 복제 방법을 무한히 반복한 문자열 P의 K번째 문자가 무엇인지 구하여라.

[입력]
첫 번째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 100)가 주어진다.
각 테스트 케이스마다 K(1 ≤ K ≤ 1018)가 주어진다.

[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,
문자열 P의 K번째 문자가 무엇인지 구하여라.

P1 = “001”
P2­ = “0010011”
P3 = “001001100011011”

위와 같이 복제가 이루어질 것이다.
따라서 3번째 문자는 1, 7번째 문자는 1, 10번째 문자는 0이다

문제 풀기

7584. 자가 복제 문자열

---

[풀이]

• P3 = “001001100011011” 에서 보면
  0이 되는 인덱스 값 : 0, 1, 3, 4, 7, 8, 9, 12
  1이 되는 인덱스 값 : 2, 5, 6, 10, 11, 13, 14

[규칙]

• 홀수인 경우 f(2n+1) = f(n)
• 4의 배수 숫자는 0이다. f(4n) = 0
• 짝수지만 4의 배수가 아닌 수는 1이다. f(4n + 2) = 1

import java.util.Scanner;

class Solution {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int tc=1; tc<=t; tc++) {
			long k = sc.nextLong() - 1;
			int n = 0;
			
			while(k >= 0) {
				// 홀수일 경우 f(2n+1) = f(n) 이므로
				// k에서 1을 빼준다음 2로 나누어 값을 구한다.
				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.format("#%d %d\n", tc, n);
		}
	}
}