boj 2698 : Adjacent Bit Counts

boj 2698 : Adjacent Bit Counts

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

생각한 시간은 길었지만 점화식은 간단하게 나온다.

1. A[n][k][e] : e로 끝나고 k개의 인접비트를 가지는 길이 n인 string의 수

2. A[1][0][0] = 1, A[1][0][1] = 1

3-1. A[n][k][0] = A[n - 1][k][1] + A[n - 1][k][0]

3-2. A[n][k][1] = A[n - 1][k][0] + A[n - 1][k - 1][1]