C# 백준 9184 신나는 함수 실행 (메모이제이션)

 

9184번: 신나는 함수 실행

IDEA

코드가 문제에 그대로 제시되어있어서 그대로 해봤다. w(11,11,11)만 해도 구하는데 몇분 걸린다. 이런 재귀호출의 경우 똑같은 매개변수로 호출된 메소드가 엄청나게 많다. 그럼 첫 호출에 어떤 값에 대한 정보를 기억해두면 두번째부터 불필요한 호출은 줄일 수 있다. 이렇게 여러번 호출될 값을 미리 저장해놓고 다음 호출에 저장된 값을 바로 출력해주는 방법을 메모이제이션 이라고 한다. 간단히 3차원 배열로 구현했다.

 

CODE

using System;
class Program
{
    static int a, b, c;
    static int[,,] w = new int[21, 21, 21];
    // 값을 저장할 배열
    static void Main()
    {
        for(int i = 0; i < 21; i++)
        {
            for(int j = 0; j < 21; j++)
            {
                for (int k = 0; k < 21; k++)
                    w[i, j, k] = int.MaxValue;
            }
        }
        while (true)
        {
            var abc = Console.ReadLine().Split();
            a = int.Parse(abc[0]); b = int.Parse(abc[1]); c = int.Parse(abc[2]);
            if (a == -1 && a == b && b == c) break;
            Console.WriteLine($"w({a}, {b}, {c}) = {W(a, b, c)}");
        }
    }
    static int W(int a, int b, int c)
    {
        if (a <= 0 || b <= 0 || c <= 0) return 1;
        else if (a > 20 || b > 20 || c > 20) return W(20, 20, 20);
        // 이 두 경우는 저장할 필요가 없다.
        // 이것까지 챙기려면 배열의 크기가 엄청 커지지만
        // 늘어난 공간에는 똑같은 값들만 저장된다.
        // 오히려 메모리 낭비
        else if (a < b && b < c)
        {
            if (w[a, b, c] == int.MaxValue) // 처음 호출된 값이면
            {
                w[a, b, c] = W(a, b, c - 1) + W(a, b - 1, c - 1) - W(a, b - 1, c);
                // 배열에 이 값을 저장한다.
                return W(a, b, c - 1) + W(a, b - 1, c - 1) - W(a, b - 1, c);
            }
            else return w[a, b, c];         // 처음이 아니면 배열의 값을 바로 return
        }
        else
        {
            if (w[a, b, c] == int.MaxValue)
            {
                w[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 W(a - 1, b, c) + W(a - 1, b - 1, c) + W(a - 1, b, c - 1) - W(a - 1, b - 1, c - 1);
            }
            else return w[a, b, c];
        }
    }
}