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

0. 제목

• 백준 9095 1,2,3 더하기
• BOJ 9095 1,2,3 더하기
• C++ 1,2,3 더하기

---

1. 문제

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

---

2. 풀이

• DP 방식을 이용하였다.
• 초기값 3개(dp[1], dp[2], dp[3])를 먼저 설정하였다.
• 1, 2, 3 을 이용하여 어떻게 기존의 값을 재사용할 수 있을까
• dp[8]을 예로 들어보면 1을 사용했을때 dp[7], 2를 사용했을때 dp[6], 3을 사용했을때 dp[5], 이 값들을 더하면 된다.
• dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

---

3. 코드

 

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int T;
    int n;
    int dp[11];
    
    cin >> T;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for(int i = 0; i < T; i++){
        cin >> n;
        for(int j = 4; j <= n; j++)
            dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
        cout << dp[n] << '\n';
    }
    return 0;
}