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

📝 문제풀이 과정

---

1 = 1 (1가지) DP[0] = 1

2 = 1 + 1 = 2 (2가지) DP[1] = 2

3 = 1 + 1 + 1 = 1 + 2 = 2 + 1 = 3 (4가지) DP[2] = 4

4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 1 + 3 = 2 + 1 + 1 = 2 + 2 = 3 + 1 (7가지) DP[3] = 7

따라서 점화식은 DP[i] = DP[i-3] + DP[i-2] + DP[i-1]

 

💻 C++ 제출코드

---

#include <stdio.h>
#include <vector>
using namespace std;

int main(){
    int T;
    scanf("%d", &T);
    for(int i=0; i<T; i++){
        int n;
        scanf("%d", &n);
        vector<int> DP(n);
        
        DP[0] = 1; DP[1] = 2; DP[2] = 4;
        
        for(int j=3; j<n; j++){
            DP[j] = DP[j-2] + DP[j-1] + DP[j-3];
        }
        
        printf("%d\n", DP[n-1]);
    }
}

• DP는 배열, vector, deque 아무거나 상관없다.

 

👏 결과

---