[백준 - C#] 9184번 신나는 함수 실행

문제링크

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

9184번: 신나는 함수 실행

 

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

조건

시간제한 : 1초
메모리 제한 : 128 MB

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다.
입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

 

문제정리

1. 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸립니다.
2. 빠르게 w(a, b, c)를 출력하는 프로그램을 구하시오.
3. 입력의 마지막은 -1 -1 -1 입니다.
4. -50 <= a, b, c <= 50

이번 문제의 경우 재귀함수로 구현되어 있는 w(a, b, c)를 더 빠르게 처리할 수 있는 방법을 찾아 구현해내는 문제입니다.

현재 dp 문제들을 풀고 있기 때문에 dp를 생각하여 문제를 풀이하였습니다.

 

함수 w는 이미 구현되어 있기 때문에 수식은 그대로 사용하며 이미 계산되어진 값들은 다시 계산할 필요가 없기 때문에 dp 라는 변수를 만들어 계산되어진 값들은 미리 저장하여 시간을 절약하였습니다.

 

재귀 함수와 동적프로그래밍 함수를 모두 코드에 표기 하였으며 두 함수를 비교해가면 쉽게 이해하실 수 있으실 것 같습니다.

 

C# 코드

static void Main(string[] args)
{
    //  https://bokhead.tistory.com/
    // 9184
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    int[,,] dp = new int[21, 21, 21];
    while (true)
    {
        int[] N = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
 
        if (N[0] == -1 && N[1] == -1 && N[2] == -1)
            break;
 
        writer.WriteLine($"w({N[0]}, {N[1]}, {N[2]}) = {Result(N[0], N[1], N[2])}");
    }
 
    writer.Close();
    reader.Close();
 
    // 동적 프로그래밍
    int Result(int a, int b, int c)
    {
        if (a <= 0 || b <= 0 || c <= 0)
            return 1;
 
        if (a > 20 || b > 20 || c > 20)
            return Result(20, 20, 20);
 
        // 이미 계산된 값이라면 계산하지 않고 리턴
        if (dp[a, b, c] != 0)
            return dp[a, b, c];
 
        if (a < b && b < c)
        {
            dp[a, b, c] = Result(a, b, c - 1) + Result(a, b - 1, c - 1)
                - Result(a, b - 1, c);
            return dp[a, b, c];
        }
 
        dp[a, b, c] = Result(a - 1, b, c) + Result(a - 1, b - 1, c)
            + Result(a - 1, b, c - 1) - Result(a - 1, b - 1, c - 1);
        return dp[a, b, c];
    }
 
    // 재귀함수
    int W(int a, int b, int c)
    {
        if (a <= 0 || b <= 0 || c <= 0)
            return 1;
 
        if (a > 20 || b > 20 || c > 20)
            return W(20, 20, 20);
 
        if (a < b && b < c)
            return W(a, b, c - 1) + W(a, b - 1, c - 1) - W(a, b - 1, c);
 
        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);
    }
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.