[백준] 9184번 신나는 함수 실행 C++ 코드

코드

#include <iostream>

using namespace std;
int a,b,c,cnt[21][21][21];

int go(int x, int y, int z) {
    if(x <= 0 || y <= 0 || z <= 0) return 1;
    if(x > 20 || y > 20 || z > 20) return go(20,20,20);
    if(cnt[x][y][z] != 0) return cnt[x][y][z]; // 값이 있으면 출력
    if(x < y && y < z) return cnt[x][y][z] = go(x,y,z-1) + go(x,y-1,z-1) - go(x,y-1,z);
    return cnt[x][y][z] = go(x-1,y,z) + go(x-1,y-1, z) + go(x-1,y,z-1) - go(x-1,y-1,z-1);
}

int main() {
    while(1) {
        cin >> a >> b >> c;
        if(a == -1 && b == -1 && c == -1) break;
        go(a,b,c);
        cout << "w(" << a << ", " << b << ", " << c << ") = " << go(a,b,c) << '\n';
    }
    return 0;
}

재귀를 계속 실행하면 시간복잡도가 급증한다. 따라서 값을 저장하는 과정이 필요하다. 함수 매개변수가 3개이므로 3차원 배열을 이용해서 값을 기록해두는 아이디어가 필요했다.