[문제]
70세 박종수 할아버지는 매일 매일 약 반알을 먹는다.
손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.
첫째 날에 종수는 병에서 약 하나를 꺼낸다.
그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.
다음 날부터 종수는 병에서 약을 하나 꺼낸다.
(약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고,
아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.
종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다.
손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다.
총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다.
이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?
[입력]
입력은 최대 1000개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.
입력의 마지막 줄에는 0이 하나 주어진다.
full : 알약 전체짜리
half : 알약 반쪽짜리
1. full == 0 이면 ,
더이상 먹을약이 없거나 half로만 이루어진다. 따라서 1
2. full짜리를 반쪽 베어먹는다면, 반쪽짜리는 하나 증가
pillArray[full-1][half+1]
3. 반쪽짜리를 먹으면, 반쪽 짜리 하나 감소, 전체짜리는 변동없음
pillArray[full][half]
package org.baekjoon;
import java.util.Scanner;
public class test4811 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int test_case = sc.nextInt();
while(test_case > 0) {
test_case--;
int n = sc.nextInt();
// 2n일 동안 먹는다
long[][] pillArray = new long[2*n+1][2*n+1];
int full = n-1; // 처음에 반알을 먹으므로 전체는 -1
int half = 1; // 처음에 반알을 먹으므로 반알짜리가 하나 생긴다.
System.out.println(n+" : "+pillCnt(full, half, pillArray));
}
}
private static long pillCnt(int full, int half, long[][] pillArray) {
if(full > 0 ) {
if(pillArray[full][half] != 0)
return pillArray[full][half];
}
// 전체 알약이 없으면 반알씩 먹는방법뿐이므로 return 1
if( full == 0) {
pillArray[full][half] = 1;
return 1;
}
else {
long sum = 0;
// 전체의 반을 먹음면 전체-1 반짜리+1
sum += pillCnt(full-1, half+1, pillArray);
// 반쪽짜리가 있으면
if(half > 0)
sum += pillCnt(full, half-1, pillArray);
pillArray[full][half] = sum;
return pillArray[full][half];
}
}
}
