[백준/C++] 15992번: 1, 2, 3 더하기 7

 

문제

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

---

문제 요약

정수 n을 m개의 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>

#define ll long long

using namespace std;

int t;

int dp[1010][1010];

ll dfs(int n, int m) {
    // 음수일 경우 0
    if (n <= 0 || m <= 0) return 0;

    // 이미 메모이제이션 테이블에 값이 있는 경우
    if (dp[n][m] != -1) return dp[n][m];

    return dp[n][m] = (dfs(n - 1, m - 1) + dfs(n - 2, m - 1) + dfs(n - 3, m - 1)) % 1000000009;
}

int main() {
    cin >> t;

    // 초기 설정
    memset(dp, -1, sizeof(dp));

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


    while (t--) {
        ll n, m;
        cin >> n >> m;

        cout << dfs(n, m) << "\n";
    }
   

    return 0;
}

---

코드 설명

1. 메모이제이션 테이블 dp를 정의한다. dp[i][j]는 정수 i를 j개의 1, 2, 3의 합으로 나타낼 수 있는 방법 수이다.

 

2. n이 1, 2, 3일 경우에 대한 dp 초기값을 설정한다. (아직 dp 값을 모르는 경우 -1)

 

3. dfs(n, m)을 통해 정수 n을 m개의 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 완전탐색(백트래킹)한다.

 

4. 탐색을 진행하면서, n과 m이 음수일 경우 방법이 없으므로 0을 반환하고, dp에 이미 값이 구해져 있다면 재귀를 진행하지 않고 즉시 값을 반환한다.