2022.02.06 [백준] C# 신나는 함수 실행

 

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

9184번: 신나는 함수 실행

---

풀이

아래의 코드는 메모이제이션과 재귀함수를 이용하여 해결하였다.

3차원 배열인 array를 선언하고 문제의 변수범위가 -50<=a,b,c<=50이라서 배열에 넣기 위해 모두 +50을 해주었다.

재귀함수를 돌리면서 나온 결과를 array에 저장하고 이후에 동일한 계산이 반복될 경우 계산하지 않고 array배열에서 가져와서 사용했다. 메모이제이션을 이용하여  top down,bottom up방식을 사용하는 것이 다이나믹 프로그래밍이라고 한다.

using System;
using System.Text;
using System.IO;
 
class Program
{
    static int[,,] array;
    static int func(int a, int b, int c)
    {
        if (array[a, b, c] != 0)
        {
            return array[a, b, c];
        }
        if (a <=50 || b <=50 || c <=50)
        {
            array[a, b, c]=1;
        }
        else if(a>70||b>70||c>70)
        {
            array[a,b,c] = func(70, 70, 70);
        }
        else if (a < b && b < c)
        {
            array[a, b, c] = func(a, b, c - 1) + func(a, b - 1, c - 1) - func(a, b - 1, c);
        }else
        {
            array[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);
        }
        return array[a, b, c];
    }
    
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        array = new int[101, 101, 101];
        while (true)
        {
            string[] s = sr.ReadLine().Split();
            int[] num = new int[3];
            for(int i = 0; i < num.Length; i++)
            {
                num[i] = int.Parse(s[i]);
            }
            if(num[0] == -1 && num[1] == -1 && num[2] == -1)
            {
                break;
            }
            if (array[num[0] + 50, num[1] + 50, num[2] + 50] == 0){
                func(num[0] + 50, num[1] + 50, num[2] + 50);
                sw.WriteLine("w({0}, {1}, {2}) = {3}", num[0], num[1], num[2], array[num[0] + 50, num[1] + 50, num[2] + 50]);
            }
            else
            {
                sw.WriteLine("w({0}, {1}, {2}) = {3}",num[0],num[1],num[2],array[num[0] + 50, num[1] + 50, num[2] + 50]);
            }
 
        }
        sr.Close();
        sw.Close();
    } 
}