(C++) - 백준(BOJ) 9184번 : 신나는 함수 실행

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

메모이제이션으로 불필요한 함수 호출을 막는 dp문제였습니다.

 

풀이방법

 1. w라는 함수를 실행하기 전에 d[a+50][b+50][c+50]값이 저장되어 있는지 확인하는 ret 참조변수를 선언 후 저장합니다. a,b,c값이 음수를 포함하므로 음수 인덱스에 접근하지 않도록 오른쪽으로 50만큼 당겨주어 저장했기 때문에 읽을 때 +50한만큼 인덱스를 가져옵니다.

 

 2. w함수를 수행한 결과를 포맷에 맞게 출력합니다.

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int a,b,c;
int d[101][101][101];
int w(int a,int b, int c){
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    int &ret = d[a+50][b+50][c+50];
    if(ret !=-1) return ret;
    if (a > 20 || b > 20 || c > 20) return ret = w(20,20,20);
    if (a < b && b < c) return ret = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
    else return ret = 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 ret;
}

int main(){
    fastio;
    memset(d,-1,sizeof(d));
    while(1){
        cin >> a >> b >> c;
        if(a == -1 && a == b && b == c) break;
        printf("w(%d, %d, %d) = %d\n", a, b, c, w(a,b,c));
    }
}