[9184번]신나는 함수 실행

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

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)

위와 같은 재귀함수를 그대로 구현했을 때 시간이 매우 오래걸리므로

DP의 메모이제이션 기법을 이용하여 풀면 되는 문제였습니다.

 

1. 인수 중에 음수가 있으면 return 1
2. 배열에 저장된 값이 있으면 바로 return
3. 배열에 저장된 값이 없으면 계산 후 return 

전체코드

#include <iostream>

using namespace std;

int memo[51][51][51];

int dp(int a, int b, int c){
    if ((a <= 0 || b <= 0) || c <= 0) {
        return 1;
    }
    if(memo[a][b][c]==0) {
        if ((a > 20 || b > 20) || c > 20) {
            memo[a][b][c] = dp(20, 20, 20);
        }
        else if(a<b && b<c){
            memo[a][b][c] = dp(a, b, c-1) + dp(a, b-1, c-1) - dp(a, b-1, c);
        }
        else{
            memo[a][b][c] = dp(a-1, b, c) + dp(a-1, b-1, c) + dp(a-1, b, c-1) - dp(a-1, b-1, c-1);
        }
    }
    return memo[a][b][c];
}

int main() {
    int a,b,c;

    while(1){
        cin>>a>>b>>c;

        if(a==-1&&b==-1&&c==-1) {
            return 0;
        }

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