[C++] BOJ_9095 1, 2, 3 더하기

문제: 백준 9095 (c++)

풀이과정

문제를 조금 나눠서 생각해 보면, 예시로 숫자 4가 있다고 했을 때

dp 점화식을 찾는 것이기 때문에 숫자 1, 2, 3, 4의 순서로 생각해 보면 편하다.

---

숫자가 1일 경우에는 1(가지 방법)

숫자가 2일 경우에는 2 (1+1, 2)

숫자가 3일 경우에는 4 (1+1, 1+2, 2+1, 3) 이다.

이렇게 숫자 3까지는 고정을 해두고, 숫자 4일 경우를 보면

7 (1+1+1+1, 1+2+1, 1+1+2, 2+1+1, 2+2, 1+3, 3+1)이다.

---

따라서 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 이 점화식을 도출해 낼 수 있다.

이 문제는 dp의 Bottom-up 방식을 생각한다면 쉽게 풀어낼 수 있을 것이다.

#include <iostream>
using namespace std ;

int main(){

    int T ;
    cin >> T ;
    
    int dp[11] ;

    dp[1] = 1 ;
    dp[2] = 2 ;
    dp[3] = 4 ;

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

    for(int i = 0; i < T; i++){
        int n ;
        cin >> n ;
        cout << dp[n] << " ";
    }
}