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

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

dp를 이용한 문제이다. 1,2 그리고 3의 합으로 이루어진 경우의 수를 구해야하므로 3가지 경우로 나누어 볼 수 있다.

• dp[i][1] -> 1로만 이루어진 경우의 수. 무조건 1이다.
• dp[i][2] -> 1과 2로 이루어진 경우의 수.
• dp[i][3] -> 1, 2와 3으로 이루어진 경우의 수.

N=3까지는 쉽게 구할 수 있다. 4부터는 dp를 이용하게 되는데 N이 1씩 커질때마다 이전 모든 경우들에 1이 붙는다고 생각해볼 수 있다. 만약 dp[i][2]를 구한다고 한다면 이전 dp에서 1로만 이루어진 경우의 수와 1과 2로 이우어진 경우의 수들의 합을 구하면 된다. dp[i][3] 또한 마찬가지이다. 대신 중복이 일어날 수 있으므로 바로 이전이 아닌 i-2, i-3에서 구해주어야 한다. 모든 경우의 수를 구한 후 입력받은 N에 따라 dp의 합을 구해 출력해주었다. 어렵지 않게 풀 수 있었던 문제였다.

#include <iostream>
#include <cstring>

using namespace std;

int N;
int dp[10001][4];

void solution() {
    dp[1][1] = 1;

    dp[2][1] = 1;
    dp[2][2] = 1;

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

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

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int T;
    cin >> T;

    solution();

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

    return 0;
}