1562 계단수
알고리즘(DP, 비트마스킹)
1
2
3
4
5
6
1. 숫자를 기록하는 num[101] 배열과, DP[101][10][1 << 10] 배열을 이용하여 DP로 품
2. 앞에서부터 길이에 맞게 숫자를 하나하나 기록해감. 기록하면서 비트마스킹으로 0~9가 있는지 표시
-> 이때 이미 표시된 비트에 또 표시하면 기록이 망가짐. 따라서 & 연산자로 검사하고 넣음
ex) int b = bit & (1 << num[deep]) ? bit : bit + (1 << num[deep]);
3. 결과값은 DP[deep][num[deep-1]][bit] 에 기록하여 DP를 구현
(num[deep-1] 인 이유는 내 구현에선 현재 deep에 기록을 하고 다음 deep으로 넘기므로 num[deep]으로 하면 기록이 망가진다.)
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define MAX_LENGTH 100
#define DIV 1000000000
#define ALL 1023
using namespace std;
int N, num[101];
long long DP[101][10][1 << 10];
long long getAnswer(int, int);
int main() {
cin >> N;
memset(DP, -1, sizeof(DP));
long long result = 0;
for (int i = 1; i <= 9; i++) {
num[0] = i;
result += getAnswer(1, 1 << i);
}
cout << result % DIV << endl;
}
long long getAnswer(int deep, int bit) {
if (deep == N) {
if (bit == ALL)
return 1;
return 0;
}
if (DP[deep][num[deep - 1]][bit] != -1)
return DP[deep][num[deep - 1]][bit];
long long result = 0;
if (num[deep - 1] != 0) {
num[deep] = num[deep - 1] - 1;
int b = bit & (1 << num[deep]) ? bit : bit + (1 << num[deep]);
result += getAnswer(deep + 1, b);
}
if (num[deep - 1] != 9) {
num[deep] = num[deep - 1] + 1;
int b = bit & (1 << num[deep]) ? bit : bit + (1 << num[deep]);
result += getAnswer(deep + 1, b);
}
return DP[deep][num[deep-1]][bit] = result % DIV;
}