BOJ : https://www.acmicpc.net/problem/15991
github : https://github.com/junho0956/Algorithm/blob/master/15991/15991/%EC%86%8C%EC%8A%A4.cpp
더하기 5번 문제에서도 %MOD 를 안해줘서 틀렸는데 이번에도 같은실수를 했습니다
그래서 고치고 다시 제출했는데 또 WA가 뜨길래 고민해봤습니다.
제 코드의 문제점은 짝수, 홀수를 고려해주지 않은 것이였고
그 이유는 합을 만드는 경우가 대칭이 이루어지기 위해서는
그 길이를 알아야했기 때문입니다.
설명은 코드에 주석처리 해놓았습니다.
|
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
|
#include <iostream>
using namespace std;
#define MOD 1000000009
typedef long long ll;
ll dp[4][100002];
ll dfs(int num, int now, int len) {
if (num < 0)return 0;
if (num == 0)return 1;
ll& res = dp[now][num];
if (res) return res;
for (int i = 1; i <= 3; i++) {
res += dfs(num - (i * 2), i, len+2)%MOD;
// WA를 받았다.
// 왜일까 생각해봤는데 대칭이 될려면 짝수 홀수를 생각해봤을 때
// 현재까지의 길이가 짝수이고 다음 수를 고려할 때, 만약 num-i가 0이 된다면 대칭이 되지만
// 현재까지의 길이가 홀수이고 다음 수를 고려할 때, 만약 num-i가 0이 된다면 대칭이 되지않는다
if (num - i == 0 && len%2 == 0) res += dfs(num - i, i, len+1) % MOD;
}
return res%MOD;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int T; cin >> T;
while (T--) {
int num; cin >> num;
ll ans = 0;
for (int i = 1; i <= 3; i++) {
ans += dfs(num - (i * 2), i, 2) % MOD;
if(num-i == 0) ans += dfs(num - i, i, 1) % MOD;
}
cout << ans % MOD << "\n";
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > BOJ' 카테고리의 다른 글
| BOJ 15993번 1, 2, 3 더하기 8 (0) | 2020.02.20 |
|---|---|
| BOJ 15992번 1, 2, 3 더하기 7 (0) | 2020.02.19 |
| BOJ 15990번 1, 2, 3 더하기 5 (0) | 2020.02.18 |
| BOJ 15989번 1, 2, 3 더하기 4 (0) | 2020.02.18 |
| BOJ 15988번 1, 2, 3 더하기 3 (0) | 2020.02.18 |