2698 인접한 비트의 개수

백준 2698 인접한 비트의 개수 https://www.acmicpc.net/problem/2698

문제에서 주어진 인접한 비트 구하는 공식은 사용하지 않았다.
1. N번째 비트가 1이라면 N-1번째 비트가 1이라면 K값이 증가할 것이고 0이라면 유지될 것이다.

2. N번째 비트가 0이라면 N-1번째 비트가 1이든 0이든 K는 유지 된다. 

$DP[K][N][M]$ : 인접한 비트수가 K인 N번째 비트가 M인 경우의 수 (M = 0 or 1)

$DP[K][N][1]$ += $DP[K-1][N-1][1]$ + $DP[K][N-1][0]$
$DP[K][N][0]$ += $DP[K][N-1][0]$ + $DP[K][N-1][1]$

#include <cstdio> int main(){     int T;     scanf("%d", &T);     while (T--){         int N, K;         int dp[101][101][2] = { 0 };           scanf("%d%d", &N, &K);         dp[0][1][0] = dp[0][1][1]  = 1;           for (int k = 0; k <= K; k++){             for (int n = 2; n <= N; n++){                 if (k - 1 >= 0)                     dp[k][n][1] += dp[k - 1][n - 1][1];                 dp[k][n][1] += dp[k][n - 1][0];                 dp[k][n][0] += dp[k][n - 1][1] + dp[k][n - 1][0];             }         }         printf("%d\n", dp[K][N][0] + dp[K][N][1]);     }     return 0; } Colored by Color Scripter

cs