(백준 c++)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)를 출력한다.

 

 

다이나믹 프로그래밍이다.

우선 조건이 있으니 메모리를 크게 잡지 않아도 된다.

a, b, c가 21 이상이면 무조건 w(20, 20, 20)을 리턴하기 때문에

크기는 3차원 배열인 dp[21][21][21]로 넉넉히 잡아도 된다.

 

그리고 w 함수를 만들어 조건대로 dp 배열에 접근하여 리턴을 해주면 된다.

전역 변수로 dp를 선언해줬으니 0으로 초기화가 된다.

그렇기 때문에 dp[a][b][c]가 0이 아니면 값을 리턴해 주면 되고,

만약 0이라면 계산을 하지 않은 경우이기 때문에 재귀를 돌려주면 된다.

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

using namespace std;

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

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

    while(1){
        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;
}