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

백준 15989 - 1, 2, 3 더하기 4

문제 링크

생각 및 접근

• 숫자 n을 1, 2, 3으로 더하되, 중복되지 않는 가짓수를 구하는 문제다.
• 정수 i를 만들 때 오름차순으로만 더할 수 있다고 가정하고, dp[i][j]를 정수 i를 만들 때 마지막으로 더한 수가 j인 경우의 수를 저장하였다.
• 정수 i를 만들 때의 case 분류
  • 기존 값에서 i를 만들기 위해 더할 수 있는 수가 1인 경우
    • 기존 값의 마지막 수가 1이 되어야 한다.
    • dp[i][1] = dp[i - 1][1];
  • 기존 값에서 i를 만들기 위해 더할 수 있는 수가 2인 경우
    • 기존 값의 마지막 수가 1 또는 2가 되어야 한다.
    • dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
  • 기존 값에서 i를 만들기 위해 더할 수 있는 수가 3인 경우
    • 기존 값의 마지막 수가 1 또는 2 또는 3이 되어야 한다.
    • dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];

코드

#include <bits/stdc++.h>
using namespace std;

int cases, n;
long long dp[10001][4];

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

    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] = 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];
    }

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

채점 결과