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

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

9184번: 신나는 함수 실행

1. 입력

-50 \(\le\) a, b, c \(\le\) 50인 정수 a, b, c

입력의 마지막은 -1, -1, -1으로 나타내며, a, b, c가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

 

2. 출력

w(a, b, c)

 

3. 풀이

먼저 문제에서 제시하는 함수를 단순 재귀 함수로 구현해 보면 아래와 같다.

int w(int a, int b, int c)
{
    if (a <= 0 || b <= 0 || c <= 0)
        return 1;
        
    else if (a > 20 || b > 20 || c > 20)
        return w(20, 20, 20);
        
    else if (a < b && 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 이상인 경우 각 값을 낮춰가며 계산을 수행하는 형태임을 알 수 있다. 즉, a, b, c의 값이 커질수록 함수의 재귀 호출 역시 증가한다.

 

단순 재귀 함수로 구현하는 것은 비효율적이며 문제의 취지에도 맞지 않으므로, 동적 계획법을 이용해 구현한다. w(a, b, c)에 대해 계산한 값을 별도의 배열에 저장하고, 함수 호출 시 이미 계산해 둔 값이면 배열의 해당 인덱스에 저장된 값을 반환하는 형태이다.

 

입력값이 a, b, c 세 개의 변수이므로 단순하게 각 a, b, c의 값을 인덱스로 하는 3차원 배열을 이용하면 될 것이다.

 

그럼 입력값의 범위가 -50 \(\le\) a, b, c \(\le\) 50이므로 각 차원의 크기는 -50 ~ 50까지 102개일까?

 

첫 두 개의 조건문을 다시 살펴보면 그럴 필요가 없다는 것을 알 수 있다.

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

함수는 a, b, c 중 하나 이상이 0 이하라면 1을 반환한다. 또, a, b, c 중 하나 이상이 20 이상이라면 w(20, 20, 20)을 반환한다.

 

즉, '실질적으로' 재귀 호출이 발생하는 범위는 세 변수가 모두 1 이상인 동시에 모두 20 이하인 경우로 한정할 수 있다.

(세 변수 중 하나 이상이 20 이상인 경우에도 재귀 호출이 발생하지만 재귀 호출 즉시 모든 변수가 20으로 수정되므로, 계산값을 따로 저장할 정도로 유의미하지 않다.)

 

따라서 계산값을 저장하는데 필요한 각 차원의 크기는 20 내지 21이라고 볼 수 있다. 인덱스가 0부터 시작하는 것을 고려해 a, b, c가 1인 경우의 값을 인덱스 0에 저장한다면 20이고, 고려하지 않는다면 21일 것이다.

 

위에서 구현한 함수에서 한정해 둔 범위를 벗어날 때를 처리하는 부분 바로 다음에 이미 계산한 적이 있는 값이 아닌지 확인하고, 이미 계산한 값이라면 계산된 값을 찾아 반환하는 명령문을 추가한다.

 

그 다음에는 계산값을 반환하는 부분을, 계산한 값을 배열에 저장하는 명령문으로 수정한다.

 

최종적으로 아래와 같이 구현했다.

#include <iostream>

int w(int a, int b, int c);

int dp[21][21][21];
int main()
{
    int a = 0;
    int b = 0;
    int c = 0;
    while (true)
    {
        std::cin >> a >> b >> c;
        if (a == -1 && b == -1 && c == -1)
            break;
        printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
    }

    return 0;
}

int w(int a, int b, int c)
{
    static int dp[21][21][21]{};
    if (a <= 0 || b <= 0 || c <= 0)
        return 1;

    else if (a > 20 || b > 20 || c > 20)
        return w(20, 20, 20);
    
    else if (dp[a][b][c] != 0)
        return dp[a][b][c];

    else if (a < b && b < c)
        dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
        
    else
        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);

    return dp[a][b][c];
}