BOJ 15992번 1, 2, 3 더하기 7

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

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

 

아!! 시간초과 때문에 되게 힘들었는데 깊은 깨달음 덕분에 문제를 해결할 수 있었습니다!!

진짜 고민많이 했었는데 코드는 분명 정답을 출력하지만 시간초과를 해결할 수 없었습니다 ㅠㅠ..

 

깨닫게 된 것은 경우의 수가 0 이 될 수 있다는 것이였습니다.

항상 문제를 풀때 dp를 전역배열로 선언해두고 건드리지 않았었는데,

이렇게 되면 디폴트값인 0이 들어가게 됩니다.

저는 원하는 dp값을 찾아 들어가는 재귀가 dp가 0이 될 수 있는 경우임에도 불구하고 계속 재귀진입을 하게 되더라구요

dp를 -1 로 초기화해놓고 시작하니 빠르게 해결할 수 있었습니다.

별거 아니지만 저한테는 dp 초기화라는 것을 한번 생각하게끔하는 문제였습니다.

 

길이를 찾는 코드의 경우 딱히 어려운 부분은 없어서 읽어보시면 이해하실 것 같습니다.

점화식 dp[i][k] 의 의미는 "현재 길이가 k일 때 i를 만들 수 있는 경우의 수" 로 보시면 될 것 같습니다.

 

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
#define MOD 1000000009
 
ll dp[1001][1001];
 
ll dfs(int num, int cnt) {
    if (cnt < 0||num<0) return 0;
    
    if (num == 0) {
        if (cnt == 0) return 1;
        else return 0;
    }
 
    ll& res = dp[num][cnt];
    if (res != -1) return res;
 
    ll ans = 0;
    for (int i = 1; i <= 3; i++) {
        ans += dfs(num - i, cnt - 1) % MOD;
    }
    return res = ans%MOD;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int T; cin >> T;
    memset(dp, -1, sizeof(dp));
    while (T--) {
        int num, m;
        cin >> num >> m;
        cout << dfs(num, m)%MOD << "\n";
    }
    return 0;
}