2698번 인접한 비트의 개수

끝나는 지점에 어떤 수가 오는지 계산하면 된다.

 

예를 들어 val[n][k][0]이라는 것은 n개의 숫자의 인접한 비트의 개수가 k개이며 마지막에 0으로 끝난다는 뜻이다.

 

그렇다면 val[n][k][0]의 값은 val[n-1][k][0]과 val[n-1][k][0]을 더해서 나타낼 수 있고

val[n][k][1]의 값은 val[n-1][k][0]과 val[n-1][k-1][1]의 합으로 나타낼 수 있다.

(val[n-1][k-1][1] -> 마지막에 1과 1이 만나서 +1이 되므로)

 

 

 

 

 

 

이 식을 이용해 풀면 된다.