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

분류 : dp

 

요구사항

n이 주어졌을때 1, 2, 3으로 n을 만들 수 있는 경우의 수 구하기

 

풀이

 

n을 만들기 위해서 d[n-1] +d[n-2] + d[n-3] 으로 만들 수 있다

n-1에서 1을 더하면 n

n-2에서 2를 더하면 n

n-3에서 3을 더하면 n이 된다

1, 2, 3으로 만들 수 있는 경우의 수는 위 3가지 이다

#include <iostream>
#include <string.h>
#include <queue>
//#include "windows.h"
#include <algorithm>
#include <list>

using namespace std;
int d[14];

int main(){
    int t;
    scanf("%d",&t);
    for(int tc=1;tc<=t;tc++)
    {
    int n;
    scanf("%d",&n);
    d[1]=1;
    d[2]=2;
    d[3]=4;
    if(n>=4){
        for(int i=4 ; i <=n ; i++){
            d[i]= d[i-3] +d[i-2] +d[i-1];
        }
    }
    cout<<d[n]<<endl;
    }
}