[백준] 알약 (java) Recursion

2020-03-31

알약 (백준> Recursion)

문제 링크

문제설명

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

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

다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

입력

입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.

예제 입력 1 복사

6
1
4
2
3
30
0

예제 출력 1 복사

132
1
14
2
5
3814986502092304


풀이

package Recursion;

import java.util.*;

public class beak_알약 {

	static long cache[][] = new long[1000][1000];
	
	public static long sol(int f, int h) {
		
		// 기저조건
		if(f==0 && h==1)
			return 1;
		
		 //이미 값이 들어있으면 바로 return 해서, 중복으로 여러번 돌지 않게 한다
		if(cache[f][h] != 0)
			return cache[f][h];
		
		//조건 1 -> full을 -1 해주고 half는 +1
		if(f != 0)
			cache[f][h] = cache[f][h] + sol(f-1, h+1);
		
		//조건 2 -> full 그대로 두고, half만 -1 해줄 때
		if(h != 0)
			cache[f][h] = cache[f][h] + sol(f, h-1);
		
		return cache[f][h];
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			int n = sc.nextInt();
			
			if(n == 0)
				break;
			else
				System.out.println(sol(n,0)); // n개와 h는 처음엔 0
		}
		
	}
}

후기 (1h)

넘… 어려워… 기저조건 따지는 것도… 식 세우는 것도…

이미 들어왔을때 한개든 반개든 먹은거다 라는 가정을 세워준다