백준 #9095: 1,2,3 더하기

난이도 : 실버3
소요시간 :  23m
사용한 풀이법 : DP

---

풀이 과정

1. dp[1] = 1 => 1 dp[2] = 1+1, 2 => 2 dp[3] = 1+1+1, 1+2, 2+1, 3 => 4 dp[4] = 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1 => 7
2. 위의 식을 잘 보면 1로 시작하는 건 곧 1+3 인거라서 3을 이루는 덧셈의 경우의 수, 즉 dp[3]만 알면 됨 2로 시작하는건 2+2라서 dp[2]만 알면되고 3으로 시작하는건 dp[1]만 알면 됨.
3. dp[5]를 예시로 들어보자
   1. 1+…. 일때는 4를 이루는 경우들만 알면 됨 ⇒ dp[4] == dp[5-1]
   2. 2+…. 일때는 3을 이루는 경우들만 알면 됨 ⇒ dp[3] == dp[5-2]
   3. 3+…. 일때는 2를 이루는 경우들만 알면 됨 ⇒ dp[2] == dp[5-3]
4. 즉 dp[n] = dp[n-1]+dp[n-2]+ dp[n-3] 이라는 아주 간단한 점화식 완성!!

작성 코드

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    int dp[12];
  
    dp[1]=1;
    dp[2]=2;
    dp[3]=4;

    for(int i=4; i<12; i++){
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
    }

    while(t--){
        int n;
        cin >> n;
        cout << dp[n]<<'\n';

    }
}