[C++, python] BOJ, 백준 15992 - 1, 2, 3 더하기 7

문제 링크

15992번: 1, 2, 3 더하기 7

문제 풀이

이 문제는 기본 DP문제의 형태를 띄고 있다. 이 문제도 동전 문제들과 비슷하다. 또, 2의 멱수의 합을 참고해도 좋을 것이다.

[C++, python] BOJ, 백준 2410 - 2의 멱수의 합

먼저, 기본적으로 DP 배열은 입력값인 n, m이 모두 1000 이하이므로 크기가 1001x1001인 2차원 배열을 만들어줄 수 있다.

이 배열은 다음과 같은 역할을 수행한다.

• DP의 0번째 행과 열은 사용하지 않는다.
• DP[4][2]인 경우라면, 4를 (1, 2, 3) 중 2개만 사용하여 만든 방법의 수를 의미한다.
• DP[1][1], DP[2][1], DP[3][1]은 모두 1개의 방법만 가질 수 있으므로 초기값으로 활용한다.

이 문제의 규칙은 다음과 같은 방식으로 동작한다.

DP[j][i]인 경우

• j - 1의 값에 1을 더해준 값이 j이므로, j - 1을 i - 1개로 나타낸 방법의 수를 구한다. -> DP[j - 1][i - 1]
• j - 2의 값에 2를 더해준 값이 j이므로, j - 2를 i - 1개로 나타낸 방법의 수를 구한다. -> DP[j - 2][i - 1]
• j - 3의 값에 3을 더해준 값이 j이므로, j - 3을 i - 1개로 나타낸 방법의 수를 구한다. -> DP[j - 3][i - 1]
• 위 세 식의 합이 j를 (1, 2, 3) 중 i개로 나타낸 방법의 수 이다. 따라서, DP[j][i] = DP[j - 1][i - 1] + DP[j - 2][i - 1] + DP[j - 3][i - 1]

이 규칙을 적용해 문제를 풀 수 있다.

정답코드

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define fast ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define ll long long

int dp[1001][1001];
int mod = 1000000009;

int main() {
    fast;
    dp[1][1] = dp[2][1] = dp[3][1] = 1;
    for (int i = 2; i < 1001; i++) {
        for (int j = 1; j < 1001; j++) {
            for (int k = 1; k < 4; k++) {
                if (j - k > 0) dp[j][i] += dp[j - k][i - 1];
                dp[j][i] %= mod;
            }
        }
    }
    int T, n, m;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        cout << dp[n][m] << "\n";
    }
    return 0;
}

python

dp = [[0] * 1001 for _ in range(1001)]
mod = 1000000009
dp[1][1] = dp[2][1] = dp[3][1] = 1
for i in range(2, 1001) :
    for j in range(1, 1001) :
        for k in range(1, 4) :
            if j - k > 0 :
                dp[j][i] += dp[j - k][i - 1]
            dp[j][i] %= mod
for _ in range(int(input())) :
    n, m = map(int, input().split())
    print(dp[n][m])