9184번: 신나는 함수 실행

9184번: 신나는 함수 실행

사용 언어: C++

 

문제 요약

재귀 호출만 생각하면 신이 난다!
다음과 같은 재귀함수 w(a, b, c)가 정의되어 있다:

if a <= 0 or b <= 0 or c <= 0:
    return 1

if a > 20 or b > 20 or c > 20:
    return w(20, 20, 20)

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

else:
    return w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

입력:
여러 줄에 걸쳐 정수 a b c가 주어진다.
모두 -1일 경우 입력 종료.

출력:
각 입력에 대해 w(a, b, c) = 결과값 형식으로 출력한다.

문제의 함정

재귀함수 구현 자체는 쉽지만,
w(15, 15, 15) 같은 값은 수백만 번 호출되는 중복 재귀가 발생한다.
그대로 구현하면 시간 초과 혹은 시간 폭탄.

풀이

메모이제이션 (Memoization)

한 번 계산한 결과는 배열에 저장해두고
다음에 같은 입력이 오면 즉시 반환한다.

• dp[a][b][c] 배열을 사용해서 캐싱
• 입력 범위는 -50 ≤ a, b, c ≤ 50 이지만,
  실제로 w()는 0 ≤ a, b, c ≤ 20까지만 캐싱하면 충분
  → a ≤ 0이면 항상 1, a > 20이면 w(20, 20, 20)로 치환되기 때문

#include <iostream>
using namespace std;

int dp[21][21][21];

int w(int a, int b, int c) {
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);

    if (dp[a][b][c] != 0) return dp[a][b][c];

    if (a < b && b < c)
        return dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
    else
        return dp[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c)
                           + w(a-1, b, c-1) - w(a-1, b-1, c-1);
}

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

    int a, b, c;
    while (true) {
        cin >> a >> b >> c;
        if (a == -1 && b == -1 && c == -1) break;

        cout << "w(" << a << ", " << b << ", " << c << ") = "
             << w(a, b, c) << '\n';
    }
    return 0;
}