문제
병에 N개의 알약이 있다. 매일 한 알을 꺼내는데, 한 알(W)이면 반 알을 다시 넣고, 반 알(H)이면 그냥 먹는다. 2N일간의 W/H 문자열 가능한 경우의 수를 구하라.
입력
여러 줄에 N이 주어지며, 0이면 종료한다 (N은 1 이상 30 이하).
출력
각 N에 대해 경우의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 1 0 | 132 1 |
풀이
카탈란 수의 점화식으로 경우의 수를 구한다.
dp[n]을 N개 알약의 경우의 수로 정의한다- 카탈란 수 점화식:
dp[n] = sum(dp[j] * dp[n-1-j])(j = 0 ~ n-1) dp[0] = dp[1] = 1,dp[2] = 2로 초기화한다- 여러 테스트 케이스에 대해 미리 계산된 값을 출력한다
핵심 아이디어: 한 알을 꺼내는 시점에서 남은 알의 배치가 독립적인 두 부분 문제로 분할되므로, 카탈란 수 점화식이 성립한다. dp[30]까지 long 범위에서 계산 가능하다.
코드
package day399;
import java.io.*;
public class Day381BOJ4811알약 {
public static long cnt = 0;
public static long dp[];
public static int n;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
dp = new long[31];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
while (true) {
n = Integer.parseInt(br.readLine());
if (n == 0)
break;
for (int i = 3; i <= 30; i++) {
cnt = 0;// 초기화
for (int j = 0; j < i; j++) {
cnt += dp[j] * dp[i - 1 - j];
}
dp[i] = cnt;
}
sb.append(dp[n] + "\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N²)
- 공간: O(N)