알고리즘
- dp를 사용
- save[101][101] 로 메모이제이션을 위한 배열을 선언
- 한 곳에는 이제까지 들어간 새로운 곡의 수, 한 곳에는 현재 깊이
- 원리
- m == 0 일때, 현재 깊이 d에서는 이전 곡의 구성이 어찌됐든 간에, 현재~끝에 나와야할 곡의 구성의 수는 같다.
- 하지만 m이 0이 아니고, 모든 곡이 나와야한다는 조건이 있으므로, 이전곡의 구성에 영향을 받는데, 이때 이전에 들어간 개별적인 곡의 수가 몇개였는지에 대해서만 생각해주면 된다.
- ex) n == 3, m == 1, d == 5 에서 a b a b c, b a b c a 는 같은 상태이다.
- 따라서 메모이제이션을 위한 배열을 위와같이 만들어주고, 적절한 조건에 따라서 dp를 진행하면 된다.
코드
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
#include <iostream>
#include <cstring>
#define DIV 1000000007
using namespace std;
int n, m, p, state[101];
long long save[101][101];
int dp(int d, int count);
int main() {
memset(save, -1, sizeof(save));
memset(state, -1, sizeof(state));
cin >> n >> m >> p;
cout << dp(0, 0);
}
int dp(int d, int count) {
if (p - d < n - count)
return 0;
if (d == p)
return 1;
if (save[count][d] != -1)
return save[count][d];
long long ans = 0;
for (int i = 0; i < n; i++) {
if (state[i] == -1 || d - state[i] > m) {
int temp = state[i], nc = count;
if (temp == -1)
nc++;
state[i] = d;
ans = (ans + dp(d + 1, nc)) % DIV;
state[i] = temp;
}
}
return save[count][d] = ans % DIV;
}