[Java] 백준 4811번 알약

다이나믹 프로그래밍 문제입니다.
알약을 먹는 규칙이 있을 때 가능한 경우의 수를 출력해야 합니다.

알약을 먹는 규칙은 다음과 같습니다.
1. 알약 하나를 반으로 쪼개서 반은 먹고 반은 다시 통에 담는다.
2. 반으로 쪼개진 알약 이라면 그대로 먹는다.

DP를 적용하기 위해 반복되는 부분이 무엇인지 찾아봅니다.
알약이 A개, 반쪽 알약이 B개 일 때
알약을 꺼내서 반으로 쪼개서 먹거나
=> (A-1) (B+1)

반쪽 알약을 꺼내서 먹는 경우로 
=> (A) (B-1)

이는 재귀 함수로 들어가게 됩니다.
위의 과정이 반복되고 똑같은 연산을 계속해서 처리하게 됩니다.

이를 DP로 처리해주기 위해서
알약A개, 반쪽 알약B개일 때 계산된 결과값을 저장해두었다면
다음 번에 재사용할 수 있습니다.

그래서 DP[알약 개수][반쪽 알약 개수]으로 계산된 값을 저장해서 재사용해주었습니다.

 

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

public class Main {
	static long[][] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		while (true) {
			long ans = 0;
			int n = Integer.parseInt(br.readLine());
			dp = new long[n + 1][n + 1];

			if (n == 0) {
				break;
			}

			ans = func(n - 1, 1);

			bw.write(ans + "\n");
		}
		bw.close();
	}

	public static long func(int pill, int half) {
		if (dp[pill][half] > 0) {
			return dp[pill][half];
		}

		if (pill == 0) {
			return 1;
		} else if (half == 0) {
			dp[pill][half] = func(pill - 1, half + 1);
		} else if (pill > 0 && half > 0) {
			dp[pill][half] += func(pill - 1, half + 1);
			dp[pill][half] += func(pill, half - 1);
		}
		return dp[pill][half];
	}
}