코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Author: kbs
 */
public class Main {
    static int N;

    static long[] memo;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();


        memo = new long[31];

        memo[0] = 1;
        memo[1] = 1;
        memo[2] = 2;

        for (int i = 3; i <= 30; i++) {
            for (int j = 0; j < i; j++) {
                memo[i] += memo[j] * memo[i - 1 - j];
            }
        }

        while (true) {
            N = Integer.parseInt(br.readLine());
            if (N == 0) break;
            sb.append(memo[N]).append("\n");
        }

        System.out.println(sb);
    }
}

• 알약을 N개 먹는다고 할 때 다음과 같은 패턴을 확인할 수 있다.
  • 처음 알약을 까고 나면 반드시 반만 남는 알약이 생김
    그러면 갈라지지 않은 알약 N-1개와 갈라진 알약 1개가 남음.
  • 갈라지지 않은 알약을 a라고 하고 갈라진 알약을 b라고 하자.
    고르는 순서를 다음과 같이 볼 수 있다.
    1)(b)aaaaaaa... -> memo[0] $\times$ memo[N-1]
    2)(ab)aaaaaa... -> memo[1] $\times$ memo[N-2]
    3)(aab)aaaaa... -> memo[2] $\times$ memo[N-3] ...
    ...
    다 더하면 N개의 알약을 먹는 경우의 수가나오게 됨.