[알고리즘/자바] 백준 4811 - 알약

4811번: 알약

 

DP를 활용해야된다고 해서 계속 수식만 만들려다 시간을 많이 잡아먹었다. 코드를 짜보고나서 더 깊게 생각하는것도 나쁘지 않은 방법. 너무 수식만드는데 얽매이지 말아야겠다. 

 

알약이 1개인 경우는 WH (1개)

알약이 2개인 경우는 WHWH , WWHH  (2개) 

 

위에서 알수 있듯이 H는 W보다 먼저 많이 나올수 없다. 알약이 2개일떄 WHHW 같은 것은 불가능하다. (병속에 H가 하나도 없는데 H를 또 뽑는건 말이 안된다. ) 

 

따라서 이 문제에서는 병속에 남은 W와 H의 수를 기억하면서 경우의 수를 만들어야한다.

 

dp[i][j] = 통속에 남은 W가 i개 일고 H가 j일때 가능한 문자열의 조합수.

 

아래는 소스코드. 결과값이 크기때문에 long 타입을 사용했다

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


public class Main {
	
	
	static long[][] dp = new long[31][31];
	
	public static void main(String[] args) throws IOException{
		
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		while(true) {
			int n = Integer.valueOf(br.readLine());
			if(n ==0) break;
			long ans = solve(n,0); //최초의 병속에는 W만 있고 H는 없다
			bw.write(ans + "\n");
		}
		
		
		bw.close();
	}
	
	public static long solve(int wCount,int hCount) {
		
		if(wCount ==0 && hCount ==0) {
			return 1; // 조합 1회 완료
		}
		else {
			
			if(dp[wCount][hCount] != 0) return dp[wCount][hCount];
			
			long ans =0;
			if(wCount != 0) { //통속에 W가있다
				ans += solve(wCount -1 , hCount +1); //새걸 꺼낸다
			}
			if(hCount != 0) { //통속에 H가 있다
				ans += solve(wCount, hCount-1 );//반개짜리를 꺼낸다
			}
			dp[wCount][hCount] = ans;
			return ans;
		}
	}

		
}