https://www.acmicpc.net/problem/16195
16195번: 1, 2, 3 더하기 9
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이하 이어야 한다.
www.acmicpc.net
1, 2, 3 더하기 9번째 문제입니다.
boj 15992 1, 2, 3 더하기 7
https://www.acmicpc.net/problem/15992 15992번: 1, 2, 3 더하기 7 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이..
emoney96.tistory.com
위의 7번째 문제와 유사한 문제입니다.
7번째 문제는 1, 2, 3을 M개 사용하여 N을 만드는 방법의 수를 구하는 문제이고,
이 문제는 1, 2, 3을 M개 이하로 사용하여 N을 만드는 방법의 수를 구하는 문제입니다.
즉 M개, M - 1개, M - 2개, ..., 1개 까지의 방법의 수를 모두 구하는 문제입니다.
그러면 dp[N][M]는 M개 이하의 수로 N을 만드는 방법의 수라고 할 수 있습니다.
7번째 문제와 똑같이 점화식은 dp[N - 1][M - 1] + dp[N - 2][M - 1] + dp[N - 3][M - 1] 이렇게 되고
M개 이하의 수로 N을 만들기 때문에 dp[N][N]을 구할 때는 dp[N - 2][N - 1]와 dp[N - 3][N - 1]의 값을 더하기때문에 값이 채워져 있어야합니다.
|
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
|
#include <iostream>
#define MOD 1000000009
using namespace std;
int dp[1001][1001];
void init() {
dp[1][1] = 1;
dp[2][1] = 1;
dp[2][2] = 2;
dp[3][1] = 1;
dp[3][2] = 3;
dp[3][3] = 4;
for (int i = 1; i <= 3; i++) {
for (int j = i + 1; j <= i + 2; j++) {
dp[i][j] = dp[i][j - 1];
}
}
for (int i = 4; i <= 1000; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = ((dp[i - 1][j - 1] + dp[i - 2][j - 1]) % MOD + dp[i - 3][j - 1]) % MOD;
}
for (int j = i + 1; j <= i + 2; j++) {
dp[i][j] = dp[i][j - 1];
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
init();
int tc, N, M;
cin >> tc;
while (tc--) {
cin >> N >> M;
cout << dp[N][M] << '\n';
}
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 1103 게임 (0) | 2021.01.22 |
|---|---|
| boj 12852 1로 만들기 2 (0) | 2021.01.22 |
| boj 15993 1, 2, 3 더하기 8 (0) | 2021.01.22 |
| boj 15992 1, 2, 3 더하기 7 (0) | 2021.01.22 |
| boj 15991 1, 2, 3 더하기 6 (0) | 2021.01.22 |