[DP]알약(백준 4811번, 자바)☆☆☆

4811번: 알약 (acmicpc.net)

4811번: 알약

 

 

 

 

 

 

[조건]

-  약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.

=> 무조건 W가 있으면 H도 있어야 한다. 

 

- 2N일이 지나면 길이가 2N인 문자열이 만들어진다. 

 

 

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

public class Main {
	
	static long dp[];

	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N;
		dp=new long[31];
		
		dp[0]=1;
		dp[1]=1;
		dp[2]=2;
		
		while(true) {
			N=Integer.parseInt(br.readLine());
			if(N==0) break;
			System.out.println(getString(N));
			
		}
		
	}
	
	static long getString(int n) {
		
		if(dp[n]>0) return dp[n];
		long result=0;
		for(int j=0;j<=n-1;j++) {
			result+=(getString(j)*getString(n-1-j));
		}
		return dp[n]=result;
	}
}