[C++] 백준 9095번 : 1, 2, 3 더하기 (S3)

#문제

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

#풀이 & 학습한 내용

마지막에 올 수 있는 수는 1,2,3 중 하나이다. 그리고 마지막 수를 빼면 같은 문제로 문제의 크기만 n-1, n-2, n-3이 되므로 dp를 이용한다. 이때 dp배열의 초깃값으로 dp[1]=1, dp[2]=2, dp[3]=4를 넣어주고 반복문으로 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]을 통해 dp[10]까지 계산한다.

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
int dp[12];
 
int main(void) {
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i <= 10; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
 
    int T = 0;
    int n = 0;
    cin >> T;
    while (T--) {
        cin >> n;
        cout << dp[n] << '\n';
    }
}