7584

static int __solution(long long mid, long long off)
{
	if (mid == off)
		return 0;
	else if (off <= 2)
		return 0;
	else if (off == 3)
		return 1;
	
	while (off < mid)
		mid /= 2;
	
	return !(__solution(mid / 2, mid - (off - mid)));
}

static int solution(void)
{
	long long K, C;
	long long mid = 1;

	cin >> K;
	C = K;

	while (C != 1) //K보다 큰 2의 n승 중 최대값을 구함.
	{
		C >>= 1;
		mid <<= 1;
	}

	return __solution(mid, K);
}

문자열의 형식은 아래와 같다.

"....." "0" f(g("....."))

 

g는 문자열을 좌우 반전시키고, f는 문자열을 전체를 반전시킨다.

그래서 임의의 K에 대해서 K는 항상 "0" 오른쪽에 있다 가정하고 풀이를 시작하였다.

즉, f(g("...")) 내에 있다고 보는 것이다.

 

001 0 011 이 있을 때, K가 7 이라면

이 문자는 맨 앞 0이 반전된 값이다.

 

그래서 아래와 같은 재귀 형식으로 답을 구할 수 있다.

f(K) = !f(new_offset)

 

(.....) "0" f(g(.....)) 에서 "0"은 2의 n승의 위치하게 된다.

그래서 "0" 에서 K 사이에 offset을 구하고, 

이 offset 을 "0" 에 위치에서 빼면 new_offset 을 구할 수 있다.

 

그래서 이 new_offset이 1, 2, 3 인 경우 까지 재귀적으로 반복하게 되는데, 이는 재귀의 탈출을 위한 최소 조건으로

보면된다.

 

또 두번째 탈출조건으로 mid와 offset이 같은 경우인 데, 이는 "0" 의 위치에서는 굳이 계산할 필요가 없기 때문이다.

 

마지막으로 offset이 mid 보다 작은 경우가 있다. 이러한 경우는 30번째 위치의 문자를 찾을 때 발견 할 수 있다.

16 < 30 이므로 mid와 K 사이의 offset은 14이다. 새로운 mid는 8이지만 offset은 2가 된다.

그래서 mid를 조정하는 것이다.

 

끝으로 나는 위 사이트에서 문제를 풀 때 주로 C++를 이용해서 입출력으로 주로 cin, cout을 쓴다.

위 코드에서 입출력을 cin, cout으로 했을 때는 15ms 나왔지만,

printf, scanf 를 썼을 때 에는 5ms가 나왔다. 

 

printf, scanf 로 입력을 받는 것을 권장하는 듯 하다.