알약 (백준 4811번)

 

문제

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

입력

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

 

풀이

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

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

 

코드

 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];
	}
}

 

복기

처음에는 알약 개수만큼의 배열을 생성해서 매 순간 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

 

결과

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