[C++] 백준/Silver/9184. 신나는 함수 실행

[Silver II] 신나는 함수 실행 - 9184

문제 설명

지문에 주어진 의사 코드 형태의 재귀 함수를 구현해서 (a, b, c) 값에 따른 결과를 출력하는 문제다.
하지만, 재귀 함수를 그대로 돌리면 당연히 타임아웃이 날 게 뻔하므로, 다른 방법을 생각해야 한다.

 

첫 번째 조건 확인

먼저, 지문에서 다음 조건을 확인할 수 있다:

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

이 조건은 a, b, c 중 하나라도 0 이하일 때, 결과가 항상 1이라는 것을 의미한다.
이 부분은 간단히 처리 가능하다.

DP 문제임을 파악하기

이 문제를 풀 때 DP 문제라는 걸 눈치챌 수 있는 포인트는 지문이 짧고 이전 값을 재활용하는 식이 들어가 있다는 점이다.
보통 이런 문제는 DP로 접근하면 된다.
재귀 호출로 매번 계산하면 시간 초과가 날 게 뻔하기 때문에, DP 배열에 값을 미리 계산해 두고 사용하는 방식이 적합하다.

DP 배열 설계

배열 크기

문제에서 입력값은 -50 ≤ a, b, c ≤ 50으로 주어진다.
하지만 실질적으로 계산해야 하는 범위는 1 ≤ a, b, c ≤ 20이다.
따라서, DP 배열 크기는 21 x 21 x 21로 설정하면 충분하다.

vector<vector<vector<int>>> dp(21, vector<vector<int>>(21, vector<int>(21, 1)));

배열 채우기

주어진 조건에 따라 값을 채운다:

1. a < b < c일 때:

   dp[i][j][k] = dp[i][j][k - 1] + dp[i][j - 1][k - 1] - dp[i][j - 1][k];
   

2. 그 외:

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

배열을 채울 때는 3중 for문을 돌려서 채우면 된다.

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

출력 처리

이제 입력값을 받아 조건에 따라 결과를 출력하면 된다.
입력값이 -1, -1, -1인 경우 프로그램을 종료하면 된다.

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

 

최종 코드

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    // DP 배열 초기화
    vector<vector<vector<int>>> dp(21, vector<vector<int>>(21, vector<int>(21, 1)));

    // DP 배열 값 채우기
    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];
                }
            }
        }
    }

    // 입력 처리 및 출력
    int a, b, c;
    cin >> a >> b >> c;
    while (!(a == -1 && b == -1 && c == -1)) {
        cout << "w(" << a << ", " << b << ", " << c << ") = ";
        if (a <= 0 || b <= 0 || c <= 0) {
            cout << 1 << '\n';
        } else if (a > 20 || b > 20 || c > 20) {
            cout << dp[20][20][20] << '\n';
        } else {
            cout << dp[a][b][c] << '\n';
        }
        cin >> a >> b >> c;
    }

    return 0;
}

정리

1. 지문이 짧고 이전 값을 재활용하는 식이 있으면 DP 문제일 가능성이 높다.
2. DP 배열 크기를 실질적으로 필요한 범위에 맞게 설정해 메모리와 시간을 절약한다.
3. 조건별로 출력 형식을 정확히 맞춘다.