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

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

15989번: 1, 2, 3 더하기 4

오랜만의 Dynamic Programming이라서 헤맸다.

처음에는 당연히 모든 경우의 수를 세볼까 했는데, 2와 3의 개수가 1의 개수에 의지하는 듯한 느낌이 든다.

 

그래서 논리적으로 접근하기 시작하면 전형적인 다이나믹 프로그래밍이다.

만약 정수 4를 합으로 나타내고, 중복은 제거하기 때문에 가장 큰 수를 앞에 둔다면

- 1로 시작하는 방법: 1 + 1 + 1 + 1

- 2로 시작하는 방법: 2 + 2 / 2 + 1 + 1

- 3으로 시작하는 방법: 3 + 1

 

1로 시작하는 수의 경우에는 맨 앞의 1을 빼면 뒷 부분은 합을 3으로 만들 때의 1로 시작하는 방법의 경우이다.

2로 시작하는 수의 경우에는 맨 앞의 2를 빼면 뒷 부분은 합을 2로 만들 때의 2로 시작하는 방법, 1로 시작하는 방법의 경우이다.

3으로 시작하는 수의 경우에는 맨 앞의 3을 빼면 뒷 부분은 합을 1로 만들 때의 1로 시작하는 방법이다.(사실 3으로 시작하는 경우도 포함해야하나 합이 1이므로)

 

#include <iostream>
#include <vector>
int dp[10000][3] = {0};
using namespace std;

int main() {
    int t, max_t = 1;
    cin >> t;
    
    vector<int> ts(t);
    for(int i = 0;i < t;i++) {
        cin >> ts[i];
        max_t = max(max_t, ts[i]);
    }
    
    dp[0][0] = 1;
    dp[1][0] = 1;
    dp[1][1] = 1;
    dp[2][0] = 1;
    dp[2][1] = 1;
    dp[2][2] = 1;
    
    
    
    for(int i = 3;i < max_t;i++) {
        for(int j = 0;j < 3;j++) {
            int value = 0;
            for(int k = 0;k <= j;k++){
                value += dp[i - j - 1][k];
            }
            dp[i][j] = value;
            // cout << i << " " << j << " " << value << endl;
        }
    }
    
    for(int i = 0;i < t;i++) {
        int testcase = ts[i] - 1;
        cout << dp[testcase][0] + dp[testcase][1] + dp[testcase][2] << '\n';
    }
}