[BOJ/C++]9095번 1,2,3 더하기

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

9095번: 1, 2, 3 더하기

하 이거 하다가 중간에 vs code 설정 실수해서 거의 2시간 날림...

 

문제

1,2,3의 합으로 나타내는 방법의 수를 구하기

 

풀이방법

첫번째는 1={1}로 1

두번째는 2={1 1, 2}로 2

세번째는 3={1 1 1, 2 1, 1 2, 3}으로 4이다.

네번째는 1+2+4=7이므로 점화식 f(n)=f(n-1)+f(n-2)+f(n-3)으로 표현할 수 있다.

 

소스코드

#include<iostream>
using namespace std;

int main(void){
    int T,n;cin>>T;
    for(int testcase=0;testcase<T;testcase++){
        cin>>n;
        int dp[n+1];
        dp[1]=1;dp[2]=2;dp[3]=4;
        for(int i=4;i<=n;i++)
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        cout<<dp[n]<<endl;
    }
}