[BOJ 18222 // C++] 투에-모스 문자열

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 18222번 문제인 투에-모스 문자열이다.
문제는 아래 링크를 확인하자.

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

18222번: 투에-모스 문자열

투에-모스 수열(Thue-Morse sequence)은 음이 아닌 정수 n번째 항의 값이 n의 2진수 표현에 들어가는 1의 개수가 홀수이면 1, 짝수이면 0인 수열이다. 

 

0부터 (2^n) - 1번째까지의 투에-모스 수열의 값을 알 때, (2^n)부터 2^(n+1) - 1번째까지의 투에-모스 수열의 값은 (문제에서의 설명과 같이) 1과 0이 뒤바뀐 형태로 나타내는데, 이는 이진수 표현에서 대응되는 숫자의 앞쪽에 새로운 1이 하나씩 추가되는 것으로 쉽게 발견해낼 수 있는 성질이다.

 

투에-모스 수열의 더 많은 성질을 알고 싶다면 위키백과를 참고하자:

https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence

 

이 문자에서는 문자열의 첫 숫자의 index를 1로 잡고 있으므로, 주어진 k에서 1을 뺀 값의 이진수 표현의 1의 개수를 세는 것으로 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int ans = 0;
	ll N; cin >> N; N--;
	while (N > 0) {
		if (N & 1) ans ^= 1;
		N >>= 1;
	}
	
	cout << ans;
}