백준 2698 인접한 비트의 개수

문제

2698 문제 링크

풀이

dp[n][k][] n은 자리수, k는 쌍의 개수.

dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
dp[i][j][1] = dp[i - 1][j - 1][1] + dp[i - 1][j][0];

예를 들어 5자리 2개의 인접한 쌍의 경우의 수를 구한다면,
5번째 자리가 0인 경우 = dp[5][2][0] = dp[4][2][0] + dp[4][2][1]
5번째 자리가 1인 경우 = dp[5][2][1] = dp[4][[1][1] + dp[4][2][0]

최종적으로 5자리 2개의 인접한 쌍이 있는 경우는 dp[5][2][0] + dp[5][2][1]

소스코드

#include "iostream"
#include "vector"
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    vector<vector<vector<int>>> dp(101, vector<vector<int>>(101, vector<int>(2)));
    dp[1][0][0] = 1;
    dp[1][0][1] = 1;
    for (int i = 2; i < 101; i++) {
        for (int j = 0; j < i; 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];
            } else {
                dp[i][j][1] = dp[i - 1][j - 1][1] + dp[i - 1][j][0];
            }

        }
    }

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n, k;
        cin >> n >> k;
        cout << dp[n][k][0] + dp[n][k][1] << '\n';
    }

    return 0;
}

어렵...😭😬🤯