[C/C++] 백준 #2698 인접한 비트의 개수(동적 계획법)

동적 계획법(Dynamic Programming)으로 문제를 풀기 위해서는, 해당 문제에 대한 모델링을 해주어야 합니다.  모델링(modeling)을 할 때에는 N의 문제를 그보다 크기가 작은 N-1이나 N/2의 문제 등 보다 작은 형태로 나누어 주어야 하죠.  보통 N-1 문제로 표현할 수 있는 경우에는 시간 복잡도가 \(O(N)\)이 되며, N/2 문제로 표현할 수 있는 문제는 \(O(\log N)\) 또는 \(O(N \log N)\) 문제로 표현될 수 있습니다.

 

Dynamic Programming

 

예를 들어서 피보나치 수열의 경우에는 N의 문제를 N-1 문제와 N-2 문제로 해결하며, 이 것을 그대로 적용하면 \(O(N)\)이 되며, 보다 적극적인 방법으로 이분 탐색을 진행한다면,  \(O(\log N)\) 복잡도로 해결할 수 있습니다.

 

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

 

이번 문제를 잘 해결 하기 위해서는 다음과 같은 점화식을 만들었습니다.

\[dp_{1,0,0} = 1, dp_{1, 0, 1} = 1 \]
\[dp_{n,k,0} = dp_{n-1,k,0} + dp_{n-1,k,1} \]
\[dp_{n,k,1} = dp_{n-1,k,0} + dp_{n-1,k-1,1} \]

이 점화식에서 \(dp_{n, k, b}\)에서 표현되는 n, k, b 의 정의입니다.  n은 총 비트의 길이입니다.  k는 인접한 비트들의 개수가 되죠.  b는 마지막 비트가 0인지, 1인지를 나타냅니다.

 

총 길이가 1이라면, 0 또는 1이 되므로, \(dp_{1,0,0} = 1\), \(dp_{1, 0, 1} = 1 \) 이 됩니다.  k 값은 항상 n보다 작을 수밖에 없습니다.

총 길이가 n-1인 비트들에 마지막에 0을 붙인다면, k의 값은 증가하지 않으며, 맨 마지막 비트가 0이든 1이든 아무 상관이 없습니다.  그래서 두개의 합으로 표현됩니다.

총 길이가 n-1인 비트들에 마지막에 1을 붙인다면, 맨 마지막 비트가 1인 경우에는 k값이 증가하며, 0인 경우는 k값이 증가하지 않겠죠.  역시 그것을 표현하면 3번째 점화식이 만들어집니다.

 

코드 설명

 

1. 문제 개요:

• 주어진 이진 수열의 길이 n과 수열에서 연속된 1의 개수 k에 따라 가능한 수열의 개수를 계산하는 문제입니다.

• 이진 수열은 0과 1로 이루어진 수열입니다.

• 예를 들어, n=4, k=2인 경우, 가능한 수열은 0011, 1100, 0110, 1001 등입니다.

2. 변수 설명:

• dp[n][k][0]와 dp[n][k][1]은 각각 길이가 n이고, 연속된 1의 개수가 k일 때 마지막 숫자가 0인 경우와 1인 경우의 수를 의미합니다.

• t는 테스트 케이스의 수를 의미합니다.

• n은 이진 수열의 길이, k는 연속된 1의 개수를 의미합니다.

3. 초기값 설정:

• dp[1][0][0] = 1 및 dp[1][0][1] = 1: 길이가 1인 이진 수열에서 연속된 1의 개수가 0일 때, 마지막 숫자가 0인 경우와 1인 경우 모두 1가지입니다.

4. 동적 프로그래밍을 통한 값 계산:

• 이중 반복문을 통해 n과 k의 범위에 대해 dp 배열을 채워 나갑니다.

• dp[n][0][0] = dp[n - 1][0][0] + dp[n - 1][0][1]: 길이가 n이고 연속된 1의 개수가 0이며 마지막 숫자가 0인 경우는 길이가 n-1이고 연속된 1의 개수가 0인 수열에서 마지막 숫자가 0이거나 1인 경우를 더한 것입니다.

• dp[n][0][1] = dp[n - 1][0][0]: 길이가 n이고 연속된 1의 개수가 0이며 마지막 숫자가 1인 경우는 길이가 n-1이고 연속된 1의 개수가 0인 수열에서 마지막 숫자가 0인 경우와 동일합니다.

5. 각 테스트 케이스 처리:

• 입력받은 t만큼의 테스트 케이스에 대해 각각 n과 k를 입력받고, 그에 대한 결과값을 출력합니다.

• 결과값은 dp[n][k][0] + dp[n][k][1]으로 계산됩니다. 이는 길이가 n이고 연속된 1의 개수가 k인 수열의 총 개수를 의미합니다.

6. 결과 출력:

• 각 테스트 케이스에 대해 위에서 계산한 수열의 개수를 출력합니다.

 

//------------------------------------------------
//    baekjoon #2698
//        - by Aubrey Choi
//        - created at 2019-06-16
//------------------------------------------------
#include <stdio.h>

//    dp(1,0,0) = 1, dp(1, 0, 1) = 1
//    dp(n,k,0) = dp(n-1,k,0) + dp(n-1,k,1)
//    dp(n,k,1) = dp(n-1,k,0) + dp(n-1,k-1,1)
int main()
{
    int t, n, k;
    static int dp[101][100][2];
    dp[1][0][0] = dp[1][0][1] = 1;
    for(n = 2; n <= 100; n++)
    {
        dp[n][0][0] = dp[n - 1][0][0] + dp[n - 1][0][1];
        dp[n][0][1] = dp[n - 1][0][0];
        for(k = 1; k < n; k++)
        {
            dp[n][k][0] = dp[n - 1][k][0] + dp[n - 1][k][1];
            dp[n][k][1] = dp[n - 1][k][0] + dp[n - 1][k - 1][1];
        }
    }
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &k);
        printf("%d\n", dp[n][k][0] + dp[n][k][1]);
    }
    return 0;
}