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

문제 링크입니다. https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

문제에 푸는 방법이 있었기에 쉽게 풀 수 있었습니다.

 

조건을 따라 사용하면 되지만, 이전에 구했던 값을 또 구한다면 시간초과가 생깁니다.

따라서 새로운 값을 구할 때마다 저장해준뒤, 재사용하면 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#define INF 987654321

using namespace std;

int a, b, c;
long long dp[21][21][21];

int solve(int x, int y, int z){
    if(x <= 0 || y <= 0 || z <= 0) return 1;
    if(x > 20 || y > 20 || z > 20) return solve(20, 20, 20);
    if(dp[x][y][z] != 0) return dp[x][y][z];
    if(x < y && y < z) dp[x][y][z] = solve(x, y, z-1) + solve(x, y-1, z-1) - solve(x, y-1, z);
    else dp[x][y][z] = solve(x-1, y, z) + solve(x-1, y-1, z) + solve(x-1, y, z-1) - solve(x-1, y-1, z-1);
    return dp[x][y][z];
}

int main(){
    cin.tie(0);
    cout.tie(0);
    while(1){
        cin >> a >> b >> c;
        if(a == -1 && b == -1 && c == -1) break;
        printf("w(%d, %d, %d) = ", a, b, c);
        cout << solve(a, b, c) << "\n";
    }
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요