취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 9184번 문제인 신나는 함수 실행이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/9184

이 문제는 메모이제이션(memoization)의 중요성을 알 수 있는 문제이다.

주어진 함수는 새로 호출하는 함수의 세 입력값의 합이 strict하게 감소하므로 유한한 횟수를 호출하면 계산이 끝날 것임을 알 수 있다.

문제에서 주어진 함수구현은 재귀적으로 함수를 호출하지만, 메모이제이션을 하지 않아 같은 계산을 매우 여러번 반복하게 된다. 이미 한번 계산했던 함수의 값을 저장해 보관하면 이러한 반복계산을 줄일 수 있다. 아래의 코드에서 이와 같은 역할을 하는 부분은 func 함수의 if (visited) 부분과, 계산값을 dp배열에 저장하는 부분이다..

아래는 제출한 소스코드이다.

#include <iostream>
typedef long long ll;
using namespace std;

bool visited[21][21][21];
ll dp[21][21][21];

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int x, y, z; cin >> x >> y >> z;
    while (!((x == -1 && y == -1 && z == -1))) {
        cout << "w(" << x << ", " << y << ", " << z << ") = " << func(x, y, z) << '\n';
        cin >> x >> y >> z;
    }
}