[Algorithm]Baekjoon 2698 :: 인접한 비트의 개수

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int t, n, k;
int dp[101][101][2] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    dp[1][0][0] = dp[1][0][1] = 1;
 
    for (int i = 2; i <= 100; ++i)
    {
        for (int j = 0; j <= i - 1; ++j)
        {
            dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
            dp[i][j][1] = dp[i - 1][j][0];
 
            if (j > 0)
            {
                dp[i][j][1] += dp[i - 1][j - 1][1];
            }
        }
    }
 
    cin >> t;
 
    while (t--)
    {
        cin >> n >> k;
 
        printf("%d\n", dp[n][k][0] + dp[n][k][1]);
    }
}
 
 
 

 

어떤식으로 해석해야할지 몰라서 다른사람 풀이를 참고했고, 다행히 잘 이해했다.

 

dp테이블은 dp[n][k][2] 이다.

예를들어 dp[3][1][0] 이면, n이 3이면서 k가 1이고 0으로 끝날때 모든 경우의 수이다.

마찬가지로 dp[3][1][1]이면, n이 3이면서 k가 1이고 1로 끝날때 모든 경우의 수이다.

 

자 그러면 dp[n][k][0]을 구하려면 어떻게 해야할까?

일단 k값이 증가하려면 반드시 1로 끝나는 경우의수 뒤에다가 1을 붙여야 k값이 증가한다.

즉, 반대로 말하면 위의 경우를 제외하고는 k값이 증가할일이 없다.

 

우리는 dp[n][k][0], 즉 뒤에 0을 붙였을 때 k값이 유지되어있어야 한다.

근데 어차피 1로끝나는거에 0을 붙이든, 0으로 끝나는거에 0을붙이든 k값은 유지된다.

그렇기 때문에 dp[n][k][0] = dp[n-1][k][0] + dp[n-1][k][1] 이 된다.

 

그렇다면 dp[n][k][1]은 어떻게 구할까?

[n][k][1]이기 때문에 뒤에 1을붙일건데, 1을 붙임으로써 발생하는 현상은 이미 언급했듯이 1로끝나는거에 1을붙이면 k값이 증가하게된다. 물론 0에다가는 붙여봤자 증가하지 않는다.

쨌든 그렇기때문에 dp[n][k][1] = dp[n-1][k][0] + dp[n-1][k-1][1] 이 된다.

dp[n-1][k][0]을 더하는 이유는 0에다가 1을붙여봤자 k값은 그대로이기 때문에 더하는것이고,

dp[n-1][k-1][1]을 더하는 이유는 1을 붙였을 때 k가 되려면, 이전에 k-1이면서 1로 끝나는거에다가 1을 붙여야하기 때문이다. 

현재 dp[n][k][1]을 구하려는 것을 잊지말자. 1을 붙였을 때 k값이여야 한다.

 

최종출력은 0으로 끝나든 1로 끝나든 n개의 비트수이면서 k를 만족하기만 하면 되니 dp[n][k][[0] + dp[n][k][1]을 출력해주면 된다.