백준(BOJ) 동적 계획법1 - 신나는 함수 실행(9184) Silver 2

https://www.acmicpc.net/problem/9184

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인 경우는 입력의 마지막을 제외하면 없다.

문제해결

다이나믹 프로그래밍을 이용하여 해결하는 문제이다. 다이나믹 프로그래밍은 어려운 문제를 작은 부분 문제로 나누어 해결하는 방법입니다. 이렇게 작은 문제들을 해결한 후에 그 해답을 저장해두고, 나중에 같은 작은 문제가 다시 등장할 때 저장된 해답을 사용하여 중복된 계산을 피하면서 전체 문제를 효율적으로 해결하는 기법이다. 이 때  가장 작은 부분 문제부터 시작하여 그것들의 해답을 이용해 점점 더 큰 문제를 해결하는 방식인 바텀업 방식이 있고 탑다운 방식은 큰 문제를 해결하기 위해 작은 부분 문제를 호출하는 재귀적인 방식 탑다운 방식이 있다.

일반적으로 계산한 값을 저장해두어 나중에 필요할 때 재사용하는 메모이제이션(memoization)을 이용해 중복 계산을 피하여 시간초과와 메모리 효율을 높일 수 있다. 

 

기억하기(Memoization)

• Recursion(Top-Down) + Memoization
  • 재귀적으로 문제를 해결하면서
    • 해결한 작은 문제의 해답을 테이블에 저장
  • 큰 문제를 해결하면서 이미 해결되었는지를 확인하고
    • 그 작은 문제가 이미 해결되었는지를 확인하고
      • 해결되었으면 테이블에 저장된 작은 문제의 해답을 사용
      • 그렇지 않다면 recursion으로 문제를 게속 해결함
  • 테이블
    • 초기값 : 문제가 해결되지 않았음을 나타내는 값으로 초기화

문제해결 방법

• 반복연산의 제거(Botto-Up Approach)
  • 작은 문제부터 시작
  • 작은 문제를 해결 후 테이블에 저장
  • 큰 문제를 해결하면서 작은 문제를 해결할 필요가 있는 경우에는, 테이블에 저장된 값 사용
    
    

위와 같은 방법중 탑다운 방식과 메모이제이션을 이용하여 초기값으로 해결된 테이블에는 해당값을 해결되지 않은 테이블에는 0을 넣어두고 재귀적으로 문제를 해결해가는 방식으로 해결이 가능하다. 기본적인 다이나믹프로그래밍 문제이지만 3차원 배열을 써야한다는 점이 어색하고 초기값을 구하기 위한 점화식을 찾는데 약간의 시간이 소요된다는 점만 주의하면 될것 같다. 

#-- 바텀업과 탑다운 방식은 아직도 정확하게 이해가 되질 않는다.. 추가적인 정리가 필요!!

// 신나는 함수 실행 9184
#include <iostream>
#include <algorithm>
#define MAXINPUT 51

using namespace std;

typedef long long ll;

ll dp[MAXINPUT][MAXINPUT][MAXINPUT];

ll w(ll a, ll b, ll c){
    if(dp[a][b][c] != 0) // 테이블에 이미 계산된 값이 저장되어 있다면 추가 계산 없이 테이블 값 반환 
        return dp[a][b][c];
    if (a > 20 or b > 20 or c > 20){ // 계산된 값이 없다면 주어진 식에 맞게 테이블 갱신
        dp[a][b][c] = w(20, 20, 20);
    } 
    else if (a < b and 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);
    // freopen("input.txt", "r", stdin);

    ll a, b, c;
    cin >> a >> b >> c;
    
    for(ll i=0; i<MAXINPUT; i++){ // i, j, k 중 1개라도 1이 들어간다면 해당 값은 무조건 1이다.
        for(ll j=0; j<MAXINPUT; j++){ // 미리 3차원 배열에 가장 작은 값부터 계산하여 테이블을 채움
            for(ll k=0; k<MAXINPUT; k++){
                if (i == 0 or j == 0 or k ==0)
                    dp[i][j][k] = 1;
            }
        }
    }
    while(true){
        if (a == -1 and b == -1 and c == -1)
            return 0; // 종료 처리
        else{
            if(a < 0 or b < 0 or c < 0) // 음수 처리
                cout << "w(" << a <<", " << b << ", " << c << ") = " << 1 << "\n";   
            else
                cout << "w(" << a <<", " << b << ", " << c << ") = " << w(a,b,c) << "\n";
            cin >> a >> b >> c;
        }
    }
    return 0;
}