BOJ 17520 - Balanced String

링크: https://www.acmicpc.net/problem/17520

풀이

균형잡힌 문자열에서 확인하는 모든 부분 문자열은 첫번째 문자를 포함한다. 즉, 앞에서부터 순차적으로 확인하여 0와 1의 개수가 1 이상 차이가 난다면 균형잡힌 문자열이 아니라는 뜻이다.

우선 무식하게 모든 경우의 수를 다 확인해볼 수 있다.

i번째 위치를 0 또는 1로 결정하면서, 균형잡힌 문자열이 되는 경우만 탐색했다.

n=3일 때, 010, 011, 100, 101 네 개의 문자열이 나온다.

n=1부터 하나씩 확인해보면 \(2, 2, 4, 4, 8, 8, \dots, 2^{n-1}, 2^{n-1}, 2^{n}, 2^{n}\) 로 규칙성이 보인다.

이제 문제는 \(f(n)=2^{\lfloor{(n+1)}/2\rfloor}~mod~16769023\) 를 구하는 문제로 바뀌었다.

\(N~\le~100,000\)이므로 fast power 알고리즘을 사용하면 빠르게 구할 수 있다. 

코드

어떻게

어떻게 저런 규칙성이 나왔을까?

확실하게 균형잡힌 문자열을 만드는 법은 0, 1을 반복하는 것이다. (그럼 번갈아가면서 1개씩 증가하므로 계속 규칙을 만족함)

첫번째 균형잡힌 문자열을 010101 이라 하면, 다음은 010110 이다. 규칙을 만족하려면 가장 뒤의 2개를 바꾸면 된다. 0과 1의 개수는 유지되고, 앞에서부터 0, 1 개수를 세더라도 차이가 1을 넘지 않기 때문이다.

n=6 이라면, 010101 에서 끝 뒤의 0과 1을 뒤집은 0101XX 가 있고, 이건 다시 01YYYY 꼴 (YYYY = 01XX, 10XX)이다.

2개씩 묶이면서 2배의 경우의 수가 나오므로 점화식을 정리해보면 \(2^{\lfloor{(n+1)}/2\rfloor}\) 가 나온다.