BOJ 15991번 1, 2, 3 더하기 6

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가 뜨길래 고민해봤습니다.

 

제 코드의 문제점은 짝수, 홀수를 고려해주지 않은 것이였고

그 이유는 합을 만드는 경우가 대칭이 이루어지기 위해서는

그 길이를 알아야했기 때문입니다.

 

설명은 코드에 주석처리 해놓았습니다.

 

#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;
}