신나는 함수 실행

문제 링크

이전문제와 똑같이 주어진 의사코드를 구현하고 메모이제이션 기법을 적용해서 시간을 줄이는 문제다. 주어지는 인자의 수가 3개라고 전혀 당황할 필요가 없다. 메모이제이션 배열을 3차 배열로 늘리기만 하면 예제에서 적용했던 메모이제이션을 그대로 적용할 수 있다.

이후에도 꾸준히 등장하겠지만 DP문제는 대부분 답에 영향을 끼치는 인자의 수만큼의 배열 차원을 생성하게 된다. 이 문제는 인자가 3개이기 때문에 3차원 배열을 생성했다. 인자가 많은 다차원 문제일수록 난이도도 높지만 반대로 어떤 요인이 영향을 미치는지만 파악해도 풀이 난이도를 크게 낮출 수 있다. “DP” 문제를 만들어야 하기 때문에 대부분의 경우 부분 문제들이 중복되도록 설계해 출제된다. 따라서 중복되는 부분 문제를 먼저 파악해서 인자를 역으로 유추해내거나 중복된다는 사실을 통해 이 문제가 DP 관련된 문제라는 통찰을 얻을 수도 있다. DP는 대부분 중복되는 부분 문제가 존재하고 이 점을 잘 분석해야 문제를 잘 풀 수 있다.

#include <iostream>
using namespace std;
 
//메모이제이션 배열
int dp[51][51][51];
 
int w(int a, int b, int c) {
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    // 이미 계산한 값이 있는 경우, 재귀 호출하지 않고 저장된 값을 리턴 ( 메모이제이션 )
    if (dp[a][b][c] != -9999) return dp[a][b][c];
    if (a > 20 || b > 20 || c > 20) return dp[a][b][c] = w(20, 20, 20);
    if(a < b && b < c) return dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    else return 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);
}
 
int main()
{
    int a, b, c;
    
	// 메모이제이션 배열 초기화
    for (int i = 0; i < 51; i++) {
        for (int j = 0; j < 51; j++) {
            for (int k = 0; k < 51; k++) {
                dp[i][j][k] = -9999;
            }
        }
    }
    
    while (true) {
        cin >> a >> b >> c;
        if (a == -1 && b == -1 && c == -1) return 0;
        cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";        
    }    
    return 0;
}