[Baekjoon] #9184번: 신나는 함수 실행

📄 문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

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

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

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)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

---

풀이

풀이과정

함수 정의는 이미 그대로 나와있고, 문제에 나와있는 것처럼 이걸 그대로 구현하면 매우 오랜 시간이 걸리므로 최적화를 해야한다.
재귀를 사용하므로, DP(Dynamic Programming)로 시도해보았다.

그냥 단순하게 w(a, b, c) 함수에 대해서 이미 값을 계산한 적이 있으면 다시 계산하지 않고 그 값을 그대로 사용하게끔 하였다.

최종 코드

#include <iostream>
#include <algorithm> 
#include <vector>

using namespace std;

int dp[21][21][21] = {};

// w 함수
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)
        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];
}

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

    while (true) {
        int a, b, c;
        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;
}

의문점

1. dp 3차원 배열 선언을 전역으로 하는 게 좋을까, 아니면 main 함수 안에서 하는 게 좋을까?
   a) 전역으로 할 때

   장점	단점
   자동으로 0으로 초기화	전역 변수 남용
   스택 크기 걱정 없음
   여러 함수에서 자유롭게 사용 가능

   b) main 안에서 할 때:

   장점	단점
   캡슐화	스택 메모리 사용

2.        if(a >=20 || b >= 20 || c >= 20)
   		   		printf("w(%d, %d, %d) = 1048576\n", a, b, c); ```
       
        
   이렇게 하면 안 되는 이유..? 어차피 w(20, 20, 20)으로 귀결돼서 똑같지 않나..
   

3. if (dp[a][b][c] != 0) 으로 값이 이미 저장되어 있는지 검사하고 있는데, 진짜 저장된 값이 '0' 그 자체일 수도 있지 않나?