백준 9184 신나는 함수 실행 / C++"

문제 : 9184

풀이 point

재귀 반복 횟수를 줄이기 위해 dp memoziation 기법을 활용한다.
미리 계산한 값들을 기록해놓는다. 미리 계산한 값을 만나면 다시 재귀를 통해
값을 구하지 않고 저장해둔 값을 준다.

풀이 방법

dp memoziation 기법을 구현한다.
피보나치 수열 dp 방식을 풀어보면 확실히 알 수 있다.
만약 계산된 값이 있다면 그 값을 주고 없다면 계산해서 준다.

코드

//백준 9184, 신나는 함수 실행 

#include <iostream>

int a, b, c;
int dp[51][51][51];

int w(int a, int b, int c){
    if(a <= 0 || b <= 0 || c <= 0) return 1;
    if(a>20 || b>20 || c>20) return w(20, 20, 20);
    if(dp[a][b][c] != 0) return dp[a][b][c];
    if(a < b && 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(){
    while(true){
        std::cin >> a >> b >> c;
        if(a == -1 && b == -1 && c == -1) break;
        std::cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << '\n'; 
    }
    return 0;
}