[C++] 백준 18222번: 투에-모스 문자열 - Divide And Conquer

https://www.acmicpc.net/problem/18222

18222번: 투에-모스 문자열

---

 

처음에 0이 존재

다음에는 이를 비트반전 시킨 문자열을 뒤에 추가한다.

이를 무한으로 반복했을 때 N번째 자리의 숫자를 구하는 문제

 

0

01

0110

01101001

0110100110010110

...

이렇게 증가하는데, 여기에는 규칙이 있다.

만약 N번째 자리의 수를 구한다면, N번째 자리의 숫자는

N - 2^x의 숫자를 반전 시킨 값이다.

N - 2^x는 1이 되거나 2가 될 때까지 반복해주면 된다.

 

쉽게 말해,

만약 17번째 자리의 숫자를 얻고 싶다면

이는 17 - 2^4인 1번 자리의 숫자를 반전 시킨 것이므로 1이 출력 될것이다.

 

0110100110010110 까지가 16자리의 투에-모스 문자열이므로

17번은 1번 자리의 숫자를 반전시킨 1임을 눈으로도 알 수 있다.

 

 

만약 20번째 자리의 숫자를 얻고 싶다면

이는 20 - 2^4인 4번 자리의 숫자를 반전 시킨 것이고,

다시 4는 4 - 2^1인  2번 자리의 숫자를 반전 시킨 것이므로

2번 자리인 1을 총 두 번의 반전을 한 숫자이므로 1이 출력 될것이다.

 

마찬가지로 0110100110010110가 16자리의 투에-모스 문자열이다.

여기서 4자리를 더 구하면 0110을 반전시킨 1001이 되고,

1001은 다시 10 + 01(10의 반전)이므로

한 번 반전된 2번 자리인 0을 반전시킨 1임을 알 수 있다.

 

#include <iostream>
using namespace std;
int main(){
    long long t=1, k, cnt=0; cin >> k;
    while((t<<1)<k) t<<=1;
    while(k>2){
        k-=t, cnt++;
        while(k<=t) t>>=1;
    }
    k==1 ? cout << cnt%2 : cout << (cnt+1)%2;
}