[2698] 인접한 비트의 개수

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

3차원 dp문제입니다.

dp정의는

dp[인덱스][인접한 비트 수][현재 비트]라고 정의할 수 있습니다.

ex)

예제로 

n = 6이고 k=2일 때를 들어보겠습니다.

만약에 

dfs를 이용하여 0,1,1,1까지 들어와서 그다음에 깊이 6까지 들어갔다왔다고 생각해보면.

1. 00111-0

2. 00111-1

이렇게 2가지의 경우가 있겠죠

인접한 비트 수가 2인 경우는 1번하나겠죠!

근데 11011라는 수로 들어왔다고 칩시다!

그 다음으로 들어갈 필요가 있을까요??

아니요 없습니다!!

이유는 위의 00111경우에서

현재 인덱스가 5이고 인접한 비트 수가 2이고 현재 비트가 1인 경우에 1가지 밖에 없다는 것을 알았기 떄문에

굳이 다시 들어갈 필요가 없는 것입니다.

00111의 경우도

마찬가지로

11011-0과

11011-1

두가지 중 1번만 가능한 경우이기 때문입니다.

ret += f(d + 1, adj, 0);

ret += f(d + 1, adj + bit * 1, 1);

이 코드에서 윗 줄은 다음 비트가 0이기 때문에 다음으로 넘어갈때 인접한 비트 수가 증가할 수 없어서 특별한 연산 없이 adj를 삽입합니다.

두번째 줄은 내 비트가 1이기 때문에 현재 비트가 무엇이냐에 따라 인접한 비트 수가 증가할 수도 있고 그대로일 수도있겠죵! 그래서 두번째 같은 식이 나옵니다.

아래는 문제의 풀코드입니다.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 101
 
using namespace std;
int n, k;
int dp[MAX_SIZE][MAX_SIZE][2];
 
int f(int d, int adj, int bit) {
    if (d == n - 1) {
        if (adj == k) return 1;
        else return 0;
    }
 
    int &ret = dp[d][adj][bit];
    if (ret != -1) return ret;
    ret = 0;
 
    ret += f(d + 1, adj, 0);
    ret += f(d + 1, adj + bit * 1, 1);
 
    return ret;
}
 
int main() {
 
    int t;
    scanf("%d", &t);
 
    while (t--) {
        scanf("%d %d", &n, &k);
        memset(dp, -1, sizeof(dp));
 
        int ret = 0;
        for (int i = 0; i < 2; i++) {
            ret += f(0, 0, i);
        }
 
        printf("%d\n", ret);
    }
    return 0;
 
}