[DP] 신나는 함수 실행(9184)(C++)

 

1. 문제 개요

 

다음과 같은 재귀함수 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)를 출력하는 프로그램을 작성하시오.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

이 문제는 다이나믹 프로그래밍을 사용해서 풀 수 있다.

다이나믹 프로그래밍은 '기억하며 풀기'라고도 말할 수 있다. 어떤 값을 여러번 구할 때 매번 처음부터 모든 과정을 거쳐서 답을 구하는 것이 아닌, 전에 기록해놓았던 답을 사용하면서 푼다.

 

이 문제는 특정 값을 계산하는 함수를 구현하되, 시간을 단축하기 위해 DP를 적용한다.

따라서 w(a,b,c) 값을 3차원 배열에 저장해두었다가 사용한다.

 

 

4. 전체 코드

 

#include <iostream>

using namespace std;

int list[52][52][52];

int w(int a,int b,int c) {
    if(a<=0 || b<=0 || c<=0)
        return 1;
    
    if(list[a][b][c] != 0)
        return list[a][b][c];
    
    if(a>20 || b>20 || c>20) {
        list[a][b][c] = w(20,20,20);
        return list[a][b][c];
    }
    
    if(a<b && b<c) {
        list[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
        return list[a][b][c];
    }
   
    list[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 list[a][b][c];
}

int main(void) {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    
    while(1) {
        if(a == -1 && b == -1 && c == -1) break;
        printf("w(%d, %d, %d) = %d\n",a,b,c,w(a, b, c));
        scanf("%d%d%d",&a,&b,&c);
    }
}