링크: 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}~mo..