[백준] 15988 1,2,3 더하기 3

처음 dp를 배우면 풀게되는 문제다

많이 틀리는 이유는 mod때문이 아닐까 싶다..!

수가 커질수있으니 매번 더하고 mod를 해줬다!

 

1,2,3으로 표현해야하므로 

현재수 d[n]을 표현하는 방법은

1. d[n-1] 에 1더하기

2. d[n-2] 에 2더하기

3. d[n-3] 에 3더하기

이렇게 3가지 방법이 있다

결국 d[n] = d[n-1]+d[n-2]+d[n-3] 이다!

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
 
ll n;
ll d[1000002];
const ll mod = 1e9+9;
 
int main(){
    scanf(" %lld",&n);
    d[1]=1;
    d[2]=2;
    d[3]=4;
    for(int i=4;i<=1000000;i++) {
        d[i]+=d[i-1];
        d[i]%=mod;
        d[i]+=d[i-2];
        d[i]%=mod;
        d[i]+=d[i-3];
        d[i]%=mod;
    }
    while(n--){
        int k; scanf(" %d",&k);
        printf("%lld\n",d[k]);
    }
}