https://www.acmicpc.net/problem/15988
15988번: 1, 2, 3 더하기 3
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
9095번 문제와 같은문제지만 N이 1000000까지이고, dp[N] % 1000000009를 출력하는 문제입니다.
https://emoney96.tistory.com/8
boj 9095 1, 2, 3 더하기
https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 정수를 1, 2, 3의 합으로만 나타내는 방법의 수를..
emoney96.tistory.com
위의 풀이처럼 dp[i]값을 채워나가는 과정에서 int의 범위를 넘어서기 때문에 중간에 1000000009로 나눠주면서 더해야합니다.
|
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
|
#include <iostream>
#define MOD 1000000009
using namespace std;
int dp[1000001];
void func() {
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int i = 4; i <= 1000000; i++) {
dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
func();
int tc, x;
cin >> tc;
while (tc--) {
cin >> x;
cout << dp[x] << '\n';
}
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 15990 1, 2, 3 더하기 5 (0) | 2021.01.22 |
|---|---|
| boj 15989 1, 2, 3 더하기 4 (0) | 2021.01.22 |
| boj 12101 1, 2, 3 더하기 2 (0) | 2021.01.22 |
| boj 9095 1, 2, 3 더하기 (0) | 2021.01.22 |
| boj 14226 이모티콘 (0) | 2021.01.22 |