알약 (백준 4811번)

 

1. 문제

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다.
손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.
종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.
종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

2. 입력

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

 

3. 풀이

먼저 나름대로 조건을 생각해 보았다.

1. w는 항상 0보다 작으면 안된다. (h도)
2. w와 h가 0이 되면 성공하고 종료.

그리고 나서 생각한 식이 $F(w,h) = F(w-1,h+1) + F(w,h-1)$ 이다.
2차원 배열 pillList[] []에 매 순간마다의 경우의 수를 저장해서 풀어나갔다.
ex) F(3,0) = F(2,1) = F(1,2) + F(2,0) = F(0,3)+F(1,1)+F(1,1) = F(0,0)+F(0,2)+F(1,0) +F(0,2)+F(1,0) = 5

 

4. 코드

 public class Main {  
    public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
	public static int C;
	public static long[][] pillList;
	
	public static void main(String[] args) throws Exception {
		
		while(true) {
		C = Integer.parseInt(br.readLine().trim());
		if(C == 0) break;
		
		pillList = new long[C+1][C+1];
		sb.append(takePills(C,0)).append("\n");	
		}
		System.out.println(sb.toString());
	}
	//pill(w,h) = pill(w-1,h+1) + pill(w,h-1)
	public static long takePills (int w, int h) throws Exception{
		//w(완전한 알약)이 0개 보다 작아지면 불가능
		if(w < 0) {
			return 0;
		}
		//알약들이 둘다 0까지 가면 다 나눈거니깐 1증가
		if(w ==0 && h ==0) {
			return 1;
		}
		//만약에 w,h일때 답이 있으면 바로 출력
		if( pillList[w][h] != 0 ) return pillList[w][h];
		//w,h에서 w를 꺼냈다고 가정할때 -> w-1,h+1한거
		pillList[w][h] = pillList[w][h] + takePills(w-1,h+1);
		//h를 꺼냈다고 가정할때 -> w,h-1한거
		if(h > 0) {
			pillList[w][h] = pillList[w][h]  + takePills(w,h-1);
		}
		return pillList[w][h];
	}
}java

 

5. 복기

처음에는 알약 개수만큼의 배열을 생성해서 매 순간 w가 h보다 작아서는 안된다는 조건하에 배열을 채워나가는 식으로 풀었다. -> 시간복잡도 $O(2^n)$ -> n = 30 에서 시간이 한세월 걸림
이후 점화식을 깨우치고 코드로 구현하기가 너무 힘들었다. 매 w와 h의 값이 덮어씌워져서 감이 안잡혔다.
사실 이 문제는 되게 유명한 유형의 문제로 DP(동적 프로그래밍)유형 문제라고 한다.
여러가지 특성중 메모리제이션이라고 파스칼의 삼각형 같이 $nCr = nCr-1 + n-1Cr$ 같은 상황에서
저장된 결과를 배열에 저장한 뒤, 다음에 계산이 필요할 때는 저장된 값을 불러와 중복을 없애 풀이하는 기법이라고 한다. -> 시간복잡도는 $O(N^2)$으로 확연하게 줄었다.

이외에도 찾아보니 벌레탐색이라는 방법이 있다고 한다. 살짝 읽어봤는데 어렵지만 많이 유용할 것 같아서 첨부한다.
http://blog.naver.com/PostView.nhn?blogId=jhc9639&logNo=221800238417&parentCategoryNo=110&categoryNo=&viewDate=&isShowPopularPosts=false&from=postView

 

6. 결과

아이디	문제 번호	결과	메모리	시간	언어	코드 길이	제출 시간
howtolivelikehuman	4811	맞았습니다!!	16620KB	100ms	Java	996B	1달 전