[PS] 백준 2698번: 인접한 비트의 개수

|

문제

내가 이해한 문제 내용

$n$과 $k$가 주어질 때, 크기가 $n$이고 인접한 비트의 개수가 $k$인 수열의 모든 경우를 구하여라.

접근 방식

  • 내가 문제를 냈기 때문에 DP라는 것은 알고 있었다.
  • 3차원 DP의 점화식
    • dp[n][k][0]=dp[n-1][k][0]+dp[n-1][k][1]
    • dp[n][k][1]=dp[n-1][k-1][1]+dp[n-1][k][0]
    • 제일 끝 숫자가 0인지 1인지를 기준으로 판단하면 되고, 이전 경우에서 0이나 1을 붙였을 때 뭐가 나오는지 파악해서 가져오면 된다.

어려웠던 점 & 배운 점

  • 3차원 DP 점화식을 생각하는 것이 상당히 어려웠다.
  • 이런 문제는 대부분이 0과 1을 사용해서 DP를 유도하는 것 같으니 기억해두자.

시간복잡도

$O(nk)$

코드

#include <cstdio>

int tc,n,k;
int dp[101][101][2];

int main(void)
{
    scanf("%d",&tc);

    while(tc--){
        scanf("%d%d",&n,&k);
        dp[1][0][0] = dp[1][0][1] = 1;
        for(int i=2; i<=n; i++){
            dp[i][0][1] = dp[i-1][0][0];
            dp[i][0][0] = dp[i-1][0][0] + dp[i-1][0][1];
            for(int j=1; j<=k; j++){
                dp[i][j][1] = dp[i-1][j-1][1] + dp[i-1][j][0];
                dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1];
            }
        }

        printf("%d\n",dp[n][k][0]+dp[n][k][1]);
    }

    return 0;
}