[백준] 4811 - 알약

1. 문제

4811번: 알약

2. 개요

완전한 알약이 N개 든 병이 있다.

날마다 병에서 알약을 꺼내 먹는다.

이 때, 꺼낸 알약이 완전하다면 반을 쪼개 먹고, 쪼개진 알약이라면 그대로 먹는다.

완전한 알약을 꺼낸 날에는 W, 반쪽짜리를 꺼낸 날에는 H를 적는다고 할 때, 만들 수 있는 문자열의 갯수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

테스트케이스를 보면 f(1) = 1, f(1) = 2, f(2) = 2, f(3) = 5, f(4) = 14 … 라는 것을 알 수 있는데

카탈란 수가 이런 규칙이라 한번 시험해 봤더니 통과했다.

카탈란 수는

$ \displaystyle C_{n+1} = \sum_{i=0}^{n} C_iC_{n-i} $

위와 같이 나타낼 수 있기 때문에 이를 이용해 dp테이블을 완성한 후 해당 인덱스의 값을 출력한다.

3-2. Python

import sys

dp = [0 for i in range(31)]
dp[0], dp[1] = 1, 1

for i in range(2, 31):
    tmp = 0
    for j in range(i):
        tmp += dp[j] * dp[i - 1 - j]

    dp[i] = tmp

while True:
    s = int(sys.stdin.readline())

    if s == 0:
        break

    print(dp[s])

3-3. C#

internal class Program
{
    static void Main(string[] args)
    {
        long[] dp = new long[31];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i < 31; i++)
        {
            long tmp = 0;

            for (int j = 0; j < i; j++)
            {
                tmp += dp[j] * dp[i - 1 - j];
            }

            dp[i] = tmp;
        }

        while (true)
        {
            int N = int.Parse(Console.ReadLine());

            if (N == 0) break;

            Console.WriteLine(dp[N]);
        }
    }
}