[백준/BOJ] 9184번: 신나는 함수 실행 ( 동적 계획법 ) - C++ 문제 풀이

문제 설명

 

문제 링크: http://www.acmicpc.net/problem/9184

 

 

풀이

문제 설명에서 말했듯이, 재귀 함수를 사용하면 구현은 쉬우나 결과를 출력하기까지 너무 오래 걸리는 단점이 있습니다.

이유를 자세히 들여다보면 같은 결과를 구하는 연산을 반복해서 수행하느라 대부분의 시간을 낭비하고 있다는 점을 알 수 있습니다.

 

그래서 이 문제는 동적 계획법을 사용하여 푸는 것이 좋겠습니다.

동적 계획법이란 전체의 문제를 작은 부분 문제로 나누어 계산한 후 결과를 저장합니다. 그리고 작은 부분의 문제를 다시 푸는 대신 저장된 결과 값을 사용하여 전체의 문제를 빠르게 푸는 방법입니다.

 

재귀 함수를 사용하는 방식과 동적 계획법은 더 작은 부분 문제를 해결해서 큰 문제를 해결한다는 점에서 유사한 면이 있습니다.

이 글에서는 먼저 재귀 함수를 사용하여 푼 후, 그 코드를 동적 계획법을 사용하는 법으로 바꾸도록 하겠습니다.

 

재귀 함수를 사용한 w(a, b, c) 함수는 다음과 같습니다.

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

    if ( a < 0) a = 0;	
    if ( b < 0) b = 0;
    if ( c < 0) c = 0;

    if ( a == 0 || b == 0 || c == 0)	// 종료 조건
        return 1;

    if ( a > 20 || b > 20 || c > 20){	// 종료 조건
        a = b = c = 20;
    }
    
    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);
}

 

동적 계획법을 사용하려면 우선 결과를 저장할 공간을 준비해야 합니다.

#define NUM 21	// 종료 조건에서 20을 넘을 수 없습니다
int cache[NUM][NUM][NUM];

 

그리고, 동적 계획법은 상향식 문제 풀이 방식입니다.

가장 작은 문제의 결과부터 저장하기 시작하여, 중간 문제를 지나 원래 문제의 결과를 도출하는 방식이죠.

 

이 문제의 가장 작은 문제는 a, b 또는 c가 0보다 작거나 같으면 결과 값이 1이 되는 문제가 되겠네요.

그래서 시작을 다음과 같이 했습니다.

for(int j = 0; j < NUM; j++){   // 초기화
    for( int k = 0; k < NUM; k++){
        cache[0][j][k] = 1;
        cache[j][0][k] = 1;
        cache[j][k][0] = 1;
    }
}

 

다음엔, 중간 부분 문제의 결과 값들을 구하기 위해서 더 작은 문제를 해결하면서 그 값을 저장하는 작업을 반복합니다.

중간 문제를 푸는 과정에서도, 이미 계산된 값을 사용하기 때문에 속도가 빠른 장점이 있습니다.

int w(int a, int b, int c){
    if ( a < 0) a = 0;
    if ( b < 0) b = 0;
    if ( c < 0) c = 0;

    if ( a == 0 || b == 0 || c == 0)
        return 1;

    if ( a > 20 || b > 20 || c > 20){
        a = b = c = 20;
    }

    // 부분 문제의 결과를 저장하기 위해 1부터 구하고자 하는 값까지 반복한다.
    for( int i = 1; i <= a; i++){
        for( int j = 1; j <= b; j++){
            for( int k = 1; k <= c; k++){
                
                if ( i < j && j < k)
                    cache[i][j][k] = cache[i][j][k-1] + cache[i][j-1][k-1] - cache[i][j-1][k];
                else
                    cache[i][j][k] = cache[i-1][j][k] + cache[i-1][j-1][k] + cache[i-1][j][k-1] - cache[i-1][j-1][k-1];
            }
        }
    }

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

 

 

 

소스 코드

#include <iostream>
using namespace std;

#define NUM 21

int cache[NUM][NUM][NUM];

int w(int a, int b, int c){
    if ( a < 0) a = 0;
    if ( b < 0) b = 0;
    if ( c < 0) c = 0;

    if ( a == 0 || b == 0 || c == 0)
        return 1;

    if ( a > 20 || b > 20 || c > 20){
        a = b = c = 20;
    }

    for( int i = 1; i <= a; i++){
        for( int j = 1; j <= b; j++){
            for( int k = 1; k <= c; k++){
                
                if ( i < j && j < k)
                    cache[i][j][k] = cache[i][j][k-1] + cache[i][j-1][k-1] - cache[i][j-1][k];
                else
                    cache[i][j][k] = cache[i-1][j][k] + cache[i-1][j-1][k] + cache[i-1][j][k-1] - cache[i-1][j-1][k-1];
            }
        }
    }

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

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int a, b, c;

    for(int j = 0; j < NUM; j++){   // 초기화
        for( int k = 0; k < NUM; k++){
            cache[0][j][k] = 1;
            cache[j][0][k] = 1;
            cache[j][k][0] = 1;
        }
    }
    
    while(true){

        cin >> a >> b >> c;

        if (a == -1 && b == -1 && c == -1)
            break;

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

        cout << "w(" << a << ", " << b << ", " << c << ") = " << ret << "\n";
    }

    return 0;
}