[백준 4811번] 알약 (java)

4811번: 알약

 

다이나믹 프로그래밍으로 문제를 해결하였다.

메모이제이션을 위해 3차원 dp배열을 생성했다. 

int[][][] dp = new int[2*N+1][2*N+1][N+1];

첫번째 인덱스는 몇일이 지났는지를 의미하고, 두번째 인덱스는 현재 시점에서 반알짜리 알약의 개수, 세번째 인덱스는 한알짜리 알약의 개수를 의미한다.

 

dp[t][h][w] : t일이 지났을 때, 반알짜리 알약의 개수가 h개이고, 한알짜리 알약의 개수가 w개일 때 가능한 모든 문자열의 개수

 

점화식을 세우면 아래와 같다.

dp[t][h][w] = dp[t-1][h+1][w] + dp[t-1][h-1][w+1]

t일이 지났을때 반알짜리 알약의 개수가 h개, 한알짜리 알약의 개수가 w개가 되기 위해서는

 

  1. t-1일에 반알짜리 알약 h+1개와 한알짜리 알약 w개가 있을 때, 반알짜리 알약을 먹는 경우

     dp[t-1][h+1][w]

 

  2. t-1일에 반알짜리 알약 h-1개와 한알짜리 알약 w+1개가 있을 때, 한알짜리 알약을 먹는 경우

     dp[t-1][h-1][w+1] 

 

이렇게 두 가지 경우가 존재한다.

 

1번의 경우에는 반알짜리 알약은 h+1개에서 h개로 줄어들고, 한알짜리 알약은 그대로이다.

따라서 t일째 되는 날, 반알짜리 알약은 h개, 한알짜리 알약은 w개가 된다.(dp[t][h][w])

 

2번은 한알짜리 알약은 w+1개에서 w개로 줄어들고, 한알짜리 알약을 반으로 쪼개서 하나는 먹고 하나는 남으므로 반알짜리 알약은 h-1개에서 h개로 하나 증가한다. 따라서 t일째 되는 날, 반알짜리 알약은 h개, 한알짜리 알약은 w개가 된다.(dp[t][h][w])

 

따라서, 위의 점화식을 바탕으로 삼중 반복문으로 메모이제이션을 하면, 

2*N일째 되는 날 나타낼 수 있는 총 문자열의 개수를 구할 수 있다.

 

전체 코드 : 

	import java.io.*;
	public class n04811 {
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	while (true) {
	int N = Integer.parseInt(br.readLine());
	if (N == 0)
	break;
	long[][][] dp = new long[2 * N + 1][2 * N + 1][N + 1];
	dp[1][1][N - 1] = 1;
	for (int t = 2; t <= 2 * N; t++) {
	for (int h = 0; h <= 2 * N; h++) {
	for (int w = 0; w <= N; w++) {
	if (h + 1 <= 2 * N)
	dp[t][h][w] += dp[t - 1][h + 1][w];
	if (h - 1 >= 0 && w + 1 <= N)
	dp[t][h][w] += dp[t - 1][h - 1][w + 1];
	}
	}
	}
	long sum = 0;
	for (int h = 0; h <= 2 * N; h++) {
	for (int w = 0; w <= N; w++) {
	sum += dp[2 * N][h][w];
	}
	}
	bw.write(sum + "\n");
	}
	bw.flush();
	}
	}

view raw 4811.java hosted with ❤ by GitHub