BOJ 15990번 1, 2, 3 더하기 5

BOJ : https://www.acmicpc.net/problem/15990

github : https://github.com/junho0956/Algorithm/blob/master/15990/15990/%EC%86%8C%EC%8A%A4.cpp

 

1, 2, 3 더하기4 문제와 같이 2차원배열로 해결하였습니다.

문제는 꽤 쉬웠는데.. 마지막에 답을 출력해줄때 %MOD를 안해줘서 계속 틀렸네요 ㅠ,,ㅠ

 

같은 수를 연속으로 사용하지 말라고 했으니, 직전에 사용한 수가 무엇인지를 알고있다가

현재 계산에서는 피해가는 식으로 재귀를 돌렸습니다.

단, dfs의 첫 시작은 지금까지와는 다르게 1,2,3 각각 확인해주셔야 합니다.

 

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define MOD 1000000009
 
ll dp[4][100002]; // dp[i][n] : i로 n을 만들수잇는 경우의 수
 
// 같은수를 "연속"해서 사용하면 안된다
// "연속" 을 체크해서 dfs를 구현한다
 
ll dfs(int num, int now) {
    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++) {
        if (i != now) res += dfs(num - i, i)%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, i)%MOD;
 
        cout << ans%MOD << "\n";
    }
 
    return 0;
}