(C++) - 백준(BOJ) 15988번 : 1, 2, 3 더하기 3

www.acmicpc.net/problem/15988

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

dp문제였습니다.

 

풀이방법

 * 답이 나올 수 있는 범위를 조심해야합니다. int범위를 초과할 수 있으므로 long long으로 변수를 선언해줘야합니다.

 * 테스트 케이스로 인해 출력이 많아지므로 c와 동기화를 끊어 입출력이 빨라지도록 합니다.

 * Modular 연산을 주의해야합니다. 덧셈에 대해 분배법칙이 성립하나 더할 때 마다 범위가 초과할 수 있으므로 매번 더할 때 마다 Modular 연산을 해줘야 합니다.

 

 i를 만드는 경우의 수는 i-1을 만드는 경우의 수 + i-2를 만드는 경우의 수 + i-3을 만드는 경우의 수입니다. 따라서 점화식을 세운다면 다음과 같습니다.

 

d[i] = d[i-1] + d[i-2] + d[i-3]

 

Code

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000009
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
//i를 1,2,3으로 나타내는 방법의 수
//d[i] = d[i-1] + d[i-2] + d[i-3];
ll t, n, d[1000001];
ll dp(ll num){
    if(num <= 0) return 0;
    if(num == 1) return 1;
    if(num == 2) return 2;
    if(num == 3) return 4;
    ll &ret = d[num];
    if(ret != -1) return ret;
    ret = 0;
    ret += (dp(num - 1) % MOD + dp(num - 2) % MOD + dp(num - 3) % MOD) % MOD;
    return ret % MOD;
}

int main(){
    fastio;
    memset(d,-1,sizeof(d));
    cin >> t;
    while(t--){
        cin >> n;
        cout << dp(n) << '\n';
    }
}