백준# 4811 - 알약

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

4811번: 알약

재귀 호출로 분류된 4811번 알약문제 입니다.

 

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
 
namespace _4811
{
    class Program
    {
        public static long[,] arr;
 
        public static long Recur(int row, int col)
        {
            if(arr[row, col] == 0)
            {
                if (row == 0)
                    arr[row, col] = 1;
 
                else if (col == 0)
                    arr[row, col] =
                        Recur(row - 1, col + 1);
 
                else
                {
                    arr[row, col] =
                        Recur(row - 1, col + 1)
                        + Recur(row, col - 1);
                }
 
                return arr[row, col];
            }
            else
            {
                return arr[row, col];
            }
 
 
        }
 
        static void Main(string[] args)
        {
            Program.arr = new long[31, 31];
            Program.Recur(30, 0);
            var list = new List<int>();
 
 
            while (true)
            {
                int num = int.Parse(Console.ReadLine());
 
                if (num == 0)
                    break;
                else
                    list.Add(num);
            }
 
            foreach (int n in list)
                Console.WriteLine(Program.arr[n, 0]);
        }
    }
}
 

이 재귀 호출의 점화식을 살펴보면

ex) 10

들어왔다고 했을 때. 반쪽 자리는 없으므로 하나짜리를 집어야 합니다.

9, 1로 분기합니다.

 

다음 두번째 부터는 좀 달라집니다.

(9, 1)은 (8, 2)와 (9, 0)으로 갈라질 수 있습니다.

 

다음 (8, 2)는 (7, 3)과 (8, 1)로 분기됩니다.

다음 (9, 0)은 (8, 1)밖에 나올 수 없습니다.

 

예외는 두가지가 있습니다.

반쪽자리가 하나도 없을 때 무조건 하나짜리를 집고 다음으로 넘겨줍니다.

하나짜리가 없다면 나올 경우는 모두 반쪽자리 이므로 갯수에 상관없이 1입니다.

 

이 과정을 재귀로 호출하면 되는데 30까지 나오면 2^30까지 호출해야 합니다.

그래서 중간에 나오는 과정을 전부 배열에 저장 했습니다.

 

배열에 값을 확인하고 계산했던적 있던거라면 해당 값을 불러오고,

처음 보는 경우라면 다시 분기하며 값을 찾아 출발합니다.

 

 

저는 가장 처음 1 ~ 30개의 한쪽짜리 알약 모두를 구해놓고 입력이 오면

값을 돌려주기만 하는 방식으로 풀었습니다.