[ boj : 18222 ] 투에-모스 문자열

www.acmicpc.net/problem/18222

18222번: 투에-모스 문자열

문제 : 제일 처음 0이 주어지고 그다음 뒤집어서 붙여줍니다. 그럼 01이 되겠죠. 이걸 또다시 뒤집어서 붙여줍니다. 그럼 0110이 됩니다. 이것을 반복해서 긴 문자열을 만든다고 합시다. 이때 k 번째에 해당하는 문자를 구하시오.

 

해설 : 먼저 일정한 규칙을 알 수 있습니다. k번째에 해당하는 문자를 구하기 위해선 k 번째가 해당하는 문자열의 길이를 구해야 하는데 이건 2의 거듭제곱으로 구할 수 있습니다.

0 - 길이 1

01 - 길이 2

0110 - 길이 4

01101001 -  길이 8

 

그 다음에 해야될 일은 k번째에 해당하는 문자는 그 전 문자열에서 뒤집어서 붙여준 문자열에 해당되니 그 전 문자열에서 k번째에 대칭되는 문자를 뒤집은 문자가 됩니다.

 

즉, k가 3이라면 0110 이 해당되는데 이건 01을 뒤집어서(10) 붙여준 것이 되니 0을 뒤집은 문자가 되겠죠

 

그럼 다 끝났습니다. 식을 세워보면 'f(x)를 x번째에 해당하는 문자' 라고 칭하면 f(1) = 0 이 되겠고,x보다 작은 2의 거듭제곱을 y라고 하겠습니다.

그러면 f(x) = 1-f(x-y) 가 됩니다. 이것을 계속 재귀적으로 구해주면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll f(ll x);

int main() {
	ll n;
	cin>>n;
	
	cout<<f(n);
	return 0;
}
ll f(ll x)
{
	if(x==1)return 0;
	ll i;
	for(i=1;i+i<x;i+=i);
	return !f(x-i);
}