https://www.acmicpc.net/problem/2698
풀이:
- a[n][k][0] : 크기가 n이고 인접비트의 수가 k이며, 끝에 비트가 0인 수
- a[n][k][1] : 크기가 n이고 인접비트의 수가 k이며, 끝에 비트가 1인 수
- a[n][k][0] = a[n - 1][k][0] + a[n - 1][k][1]
- a[n][k][1] = a[n - 1][k][0] + a[n - 1][k - 1][1]
코드:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <iostream>
using namespace std;
int a[102][102][2] = { 0 };
int main(void) {
int T, n, k;
int cnt = 2;
cin >> T;
a[1][0][1] = 1; a[1][0][0] = 1;
for (int i = 0; i < T; i++) {
cin >> n >> k;
for (int t = cnt; t < n + 1; t++) {
for (int y = 0; y < t; y++) {
a[t][y][0] = a[t - 1][y][0] + a[t - 1][y][1];
a[t][y][1] = a[t - 1][y][0] + a[t - 1][y - 1][1];
}
}
cout << a[n][k][0] + a[n][k][1] << endl;
cnt = n;
}
return 0;
}
|