[백준/Baekjoon] 15988 1, 2, 3 더하기 3 C++ :: Dynamic Programming

https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

---

1. Logic

재귀로 들어가서 0이 되면 경우의 수 1을 count해준다.

다만 숫자가 크기 때문에 타입을 long long 으로 해줬다.

---

2. Code

#include <iostream>
#include <cstring>

using namespace std;

long long dp[1000001];

long long solve(long long n) {
    if(n == 0) return 1;
    else if(n < 0) return 0;
    
    long long &ret = dp[n];
    
    if(ret != -1) return ret;
    
    ret = 0;
    
    ret += solve(n - 1);
    ret += solve(n - 2);
    ret += solve(n - 3);
    
    return ret %= 1000000009;
} 

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
    
    int t;
    cin >> t;
    
    while(t--) {
        int num;
        cin >> num;
        
        cout << solve(num) << '\n';
    }
    
}

 

 

---

3. Feedback

항상 출력 형식또한 꼼꼼하게 볼 것.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐