2698 인접한 비트의 갯수

#include <stdio.h>
 
int arr[1005][2] = { 0 };
int dp[105][105][2] = { 0 };
 
int main() {
    int t;
    scanf("%d", &t);
 
    int maxN = 0, maxK = 0;
    for (int i = 1; i <= t; i++) {
        scanf("%d %d", &arr[i][0], &arr[i][1]);
 
        if (maxN < arr[i][0]) 
            maxN = arr[i][0];
        if (maxK < arr[i][1])
            maxK = arr[i][1];
    }
 
    dp[1][0][0] = 1;
    dp[1][0][1] = 1;
    for (int i = 2; i <= maxN; i++) {
        for (int j = 0; j <= maxK; j++) {
            dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1];
 
            if(j!=0)
                dp[i][j][1] = dp[i - 1][j][0] + dp[i - 1][j - 1][1];
            else 
                dp[i][j][1] = dp[i - 1][j][0];
        }
    }
 
    for (int i = 1; i <= t; i++) {
        int n = arr[i][0];
        int k = arr[i][1];
        int rst = dp[n][k][0] + dp[n][k][1];
 
        printf("%d\n", rst);
    }
}