백준 9184번 신나는 함수 실행 - C++ 풀이

---

 

1. 메모이제이션을 통해 시간을 줄일 수 있다.
2. 재귀 함수를 똑같이 구현하되, 이미 구했던 값이라면 재귀호출을 하지 않고 저장해둔 값을 바로 리턴한다.

 

1. 메모이제이션을 통해 시간을 줄일 수 있다.

 단순한 재귀 호출을 통해 w(a, b, c)를 구할 경우 중복되는 호출이 많아진다. 20 이하의 a, b, c 에 대해서만 구해주면 되므로 총 구해야 하는 함수값은 20^3개 뿐이다. 모든 (a, b, c)에 대해 w(a, b, c) 값을 저장해두자.

 

2. 재귀 함수를 똑같이 구현하되, 이미 구했던 값이라면 재귀호출을 하지 않고 저장해둔 값을 바로 리턴한다.

 재귀 함수를 똑같이 구현하되, 만약 이미 구했던 값이라면 재귀호출을 하지 않고 저장해두었던 값을 바로 리턴해주면 된다.

 

---

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

const int MAX = 21;

int cache[MAX][MAX][MAX];

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    
    while (true) {
        int a, b, c;
        cin >> a >> b >> c;
        
        if (a == -1 && b == -1 && c == -1) {
            break;
        }
        
        cout << "w(" << a << ", " << b << ", " << c << ") = " << dp(a, b, c) << "\n";
    }
    
    return 0;
}