[C++] 백준 9184번 신나는 함수 실행

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

풀이

문제에서 재귀로 구현하면 매우 오랜 시간이 걸린다고 했으므로, DP bottom-up 방식을 이용하여 주어진 재귀함수의 내용을 iteration으로 구현했다.

그리고 여러 개의 테스트 케이스가 주어지므로 입력을 받을 때마다 DP를 수행하는 것이 아니라,
처음에 DP를 수행하여 dp[i][j][k]의 값을 모두 구해놓은 후, 문제의 조건에 맞게 w(a, b, c)에 대응하는 dp 값을 출력하였다.

재귀 함수의 내용을 살펴보았을 때, a, b, c가 어떤 값으로 들어오든 dp[i][j][k]는 i, j, k가 0 이상이고 20 이하일 때만 구해놓으면 된다.

1. 우선 DP를 수행하기 위한 초기값을 설정해야 한다.

재귀함수의 탈출 조건은 아래와 같았다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

따라서 i, j, k 중 하나라도 0인 경우에 dp[i][j][k]를 1로 초기화한다.

2. DP를 수행한다.

i, j, k가 1 이상 20이하일 때, 점화식에 따라 dp[i][j][k]를 저장해둔다.

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

3. 입력값에 따라 dp를 출력한다.

코드

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

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

    int dp[21][21][21] = {0};
    
    // dp 채워놓기
    for(int i=0; i<=20; i++) {
        for(int j=0; j<=20; j++) {
            for(int k=0; k<=20; k++) {
                if(i == 0 || j == 0 || k == 0) {
                    dp[i][j][k] = 1;
                }
            }
        }
    }

    for(int i=1; i<=20; i++) {
        for(int j=1; j<=20; j++) {
            for(int k=1; k<=20; k++) {
                if(i < j && j < k) {
                    dp[i][j][k] = dp[i][j][k-1] + dp[i][j-1][k-1] - dp[i][j-1][k];
                }
                else {
                    dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k] + dp[i-1][j][k-1] - dp[i-1][j-1][k-1];
                }
            }
        }
    }
    
    // 입력받아서 dp 값 출력
    int a, b, c;
    while(cin >> a >> b >> c) {
        if(a == -1 && b == -1 && c == -1) break;

        cout << "w(" << a << ", " << b << ", " << c << ") = ";
        if(a <= 0 || b <= 0 || c <= 0) {
            cout << 1;
        }
        else if(a > 20 || b > 20 || c > 20) {
            cout << dp[20][20][20];
        } else {
            cout << dp[a][b][c];
        }
        cout << '\n';
    }

    return 0;
}