[백준 15989번] 1, 2, 3 더하기 4 (C++)

문제링크 : https://www.acmicpc.net/problem/15989

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

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int dp[100001][4];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;

    dp[1][1] = 1;
    dp[2][1] = dp[2][2] = 1;
    dp[3][1] = dp[3][2] = dp[3][3] = 1;
    
    for(int i=4; i<10001; i++)
    {
        dp[i][1] = dp[i-1][1];  //i를 1로 만드는 경우
        dp[i][2] = dp[i-2][1] + dp[i-2][2]; //i를 1, 2로 만드는 경우
        dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3]; //i를 1, 2, 3으로 만드는 경우
    }

    int N;
    while(T--)
    {
        cin >> N;
        cout << dp[N][1] + dp[N][2] + dp[N][3] << "\n";
    }

    return 0;
}

먼저 중복을 제거하기 위해 수를 오름차순으로 생각해준다.

 

i에 대해 1로 만드는 경우의 수 -> dp[i][1]

i에 대해 2로 만드는 경우의 수 -> dp[i][2]

i에 대해 3으로 만드는 경우의 수 -> dp[i][3]

 

dp[i][2]의 경우는 앞에 1이 와도 되고, dp[i][3]은 앞에 1과 2과 와도 된다.

이를 고려하여 dp[i][2]는 1로 만드는 경우의 수도 고려하고,

dp[i][3]은 1과 2로 만드는 경우의 수를 고려하여 dp식을 세운다.

 

예를 들어 i를 4로 생각하면

dp[4][1] = 4를 1로 만드는 경우의 수이고, 앞에 1밖에 못오므로 무조건 1이다.

dp[4][2] = 4를 2로 만드는 경우의 수이고, 여기서 2를 1로 만드는 경우의 수와 2로 만드는 경우의 수를 더한다.

dp[4][3] = 4를 3으로 만드는 경우의 수이고, 여기서 4는 3과 1로 밖에 못만드므로 dp[4][1]의 값인 1만 할당된다.