[BOJ] 2698번: 인접한 비트의 개수

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

D[n][k][lb]: 길이가 n이고 연속된 비트가 k개이면서 마지막 비트가 lb(0 또는 1)인 수열의 개수

처음에는 D[n][k]으로만 점화식을 세워보려고 했는데 끄적끄적하다 보니 결국에는 마지막 비트와 관계가 있어서 어쩔 수 없이 사용하게 되었다.

마지막 비트가 0일 때

D[n][k][lb] = D[n - 1][k][0] + D[n - 1][k][1]

마지막 비트가 0인데 길이는 n이고 연속된 비트가 k인 수열의 개수는 길이 n-1짜리에서 마지막 비트가 0, 1인 두 개의 수를 합치면 된다.

ex) 11100, 01110 -> 1110에서 0하나 붙이면 되고, 0111에서 0하나 붙이면 된다.

마지막 비트가 1일 때

D[n][k][lb] = D[n - 1][k][0] + D[n - 1][k - 1][1]

마지막 비트가 0이고 k개 연속 비트 수에 1를 추가하면 되고, 마지막 비트가 1이고 k - 1개 연속 비트에 1를 붙이면 k개 연속 비트가 된다.

ex) 00111, 10111, 11101, 11011 또한 위의 점화식을 생각해보면 된다.

 

 

#include <cstdio>
#include <cstring>

int D[101][101][2];

int AdjBits(int n, int k, int lb)
{
    if (n < 0 || k < 0) return 0;
    if (D[n][k][lb] >= 0) return D[n][k][lb];

    if (lb == 0) D[n][k][lb] = AdjBits(n - 1, k, 0) + AdjBits(n - 1, k, 1);
    else D[n][k][lb] = AdjBits(n - 1, k, 0) + AdjBits(n - 1, k - 1, 1);
    //printf("D[%d][%d][%d]: %d\n", n, k, lb, D[n][k][lb]);
    return D[n][k][lb];
}

int main()
{
    memset(D, -1, sizeof D);
    D[0][0][0] = 1;
    /*D[1][1][1] = 1;
    D[1][1][0] = D[1][0][1] = D[1][0][0] = 0;*/
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, k;
        scanf("%d %d", &n, &k);
        printf("%d\n", AdjBits(n, k, 0) + AdjBits(n, k, 1));
    }
    return 0;
}