https://www.acmicpc.net/problem/12996
12996번: Acka
첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다. (1 ≤ S ≤ 50, 1 ≤ dotorya, kesakiyo, hongjun7 ≤ S)
www.acmicpc.net
N곡을 세 사람이 나눠서 불러 앨범을 완성해야 합니다.
정확히 N곡을 불러야하며, 세 사람의 기회가 모두 소진되어야 합니다.
그러면 경우의 수를 얻는 조건은 N이 0이되면서 세 사람의 기회가 모두 0이 되는 경우에만 1을 추가합니다.
dp[N][x][y][z]: N곡이 남았고, 세 사람의 기회가 x, y, z만큼 있을 때 앨범을 완성할 수 있는 경우의 수
한 곡에 대해 부를 수 있는 경우는 아래와 같습니다.
- 세 사람 중 적어도 한 명 이상이 불러야 한다.
- 세 사람 모두가 한 곡을 불러도 된다.
- 세 사람 중 두 사람이 한 곡을 불러도 된다.
- 세 사람 중 한 사람이 한 곡을 불러도 된다.
이 문제는 간단하게 위의 경우를 하나씩 모두 구해주시면 되겠습니다.
경우의 수를 더하면서 % MOD 연산을 해주도록 합시다.
|
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <iostream>
#include <cstring>
#define MAX 51
#define MOD 1000000007
using namespace std;
int dp[MAX][MAX][MAX][MAX];
int N, x, y, z;
int solve(int n, int a, int b, int c) {
if (!n) {
return !a && !b && !c;
}
int& ret = dp[n][a][b][c];
if (ret != -1) return ret;
ret = 0;
if (a && b && c) {
ret = (ret + solve(n - 1, a - 1, b - 1, c - 1)) % MOD;
}
if (a && b) {
ret = (ret + solve(n - 1, a - 1, b - 1, c)) % MOD;
}
if (a && c) {
ret = (ret + solve(n - 1, a - 1, b, c - 1)) % MOD;
}
if (b && c) {
ret = (ret + solve(n - 1, a, b - 1, c - 1)) % MOD;
}
if (a) {
ret = (ret + solve(n - 1, a - 1, b, c)) % MOD;
}
if (b) {
ret = (ret + solve(n - 1, a, b - 1, c)) % MOD;
}
if (c) {
ret = (ret + solve(n - 1, a, b, c - 1)) % MOD;
}
return ret;
}
void func() {
memset(dp, -1, sizeof(dp));
cout << solve(N, x, y, z) << '\n';
}
void input() {
cin >> N >> x >> y >> z;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 25427 DKSH를 찾아라 (0) | 2023.05.21 |
|---|---|
| boj 25682 체스판 다시 칠하기 2 (0) | 2023.02.26 |
| boj 14450 Hoof, Paper, Scissors (Gold) (0) | 2022.12.30 |
| boj 14453 Hoof, Paper, Scissors (Silver) (0) | 2022.12.30 |
| boj 2281 데스노트 (0) | 2022.10.08 |