[BOJ] 백준 2698 - 인접한 비트의 개수

문제 링크

www.acmicpc.net/problem/2698

2698번: 인접한 비트의 개수

 

풀이

$\text{D}[i][j][\text{cnt}]$: $i$번째 비트가 $j$이고, 그때 남은 인접한 비트의 수가 $cnt$일 때 조건을 만족하는 수열의 개수

$j$는 $0$ 또는 $1$입니다.

 

다음과 같이 전개될 수 있습니다.

$$\text{D}[i][j][\text{cnt}] = \text{D}[i+1][0][\text{cnt}] + \begin{cases}\text{D}[i+1][1][\text{cnt}-1]&(j = 1)\\\text{D}[i+1][1][\text{cnt}]&(j = 0)\end{cases}$$

 

현재 $j$가 1이고, 다음 $j$도 1이면 카운트를 하나 감소시켜주고, 그게 아니라면 카운트를 유지합니다.

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vs = vector<string>;
using vd = vector<double>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vvpii = vector<vpii>;
using vvpll = vector<vpll>;
using vvs = vector<vs>;

int t;
int n, k;
int d[111][2][111];

int go(int i, int j, int cnt) {
    if (cnt < 0) return 0;
    if (i == n) return cnt == 0;
    int &ret = d[i][j][cnt];
    if (ret != -1) return ret;

    int v1 = go(i + 1, 1, j == 1 ? cnt - 1 : cnt);
    int v2 = go(i + 1, 0, cnt);

    return ret = v1 + v2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;
    while (t--) {
        cin >> n >> k;
        memset(d, -1, sizeof(d));
        cout << go(0, 0, k) << '\n';
    }
}