[Java] 백준 17208번 카우버거 알바생

다이나믹 프로그래밍 문제입니다.
남은 치즈버거와 감자튀김으로 최대 몇개의 주문까지 처리할 수 있는지  찾아야 합니다.

DP배열을 3차원으로 만들어줍니다.
DP[a번째 주문][b개 치즈버거 남음][c개 감자튀김 남음]으로 나타 낼 수 있습니다.

재귀함수를 통해서 모든 주문에 대해서 확인합니다.
이번 주문을 받는 경우와 안 받고 넘어가는 경우 2가지로 재귀를 돌립니다.
이미 DP 값이 저장되어 있는 경우 그대로 가져와서 사용해주었습니다.

if (arr[index+1][0] <= b && arr[index+1][1] <= p) {
    dp[index][b][p] = knapsack(index + 1, b - arr[index+1][0], p - arr[index+1][1]) + 1;
}
dp[index][b][p] = Math.max(dp[index][b][p], knapsack(index + 1, b, p));

현재 개수로 처리 이번 주문을 처리할 수 있다면 위의 if문에 들어갑니다.
주문을 받는 경우, 안 받는 경우에 대한 코드입니다.
점화식은 위와 같은 모양으로 만들 수 있습니다.

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 int ans;
	static int n;
	static int m;
	static int k;
	static int[][] arr;
	static int[][][] 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));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		arr = new int[n + 1][2];
		dp = new int[n + 1][m + 1][k + 1];

		for (int i = 1; i <= n; ++i) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}

		for(int i=0; i<=n; ++i) {
			for(int j=0; j<=m; ++j) {
				for(int l=0; l<=k; ++l) {
					dp[i][j][l] = -1;
				}
			}
		}
		ans = knapsack(0, m, k);

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

	public static int knapsack(int index, int b, int p) {
		if (index == n) {
			return 0;
		}
		if (dp[index][b][p] >= 0) {
			return dp[index][b][p];
		}
		if (arr[index+1][0] <= b && arr[index+1][1] <= p) {
			dp[index][b][p] = knapsack(index + 1, b - arr[index+1][0], p - arr[index+1][1]) + 1;
		}
		dp[index][b][p] = Math.max(dp[index][b][p], knapsack(index + 1, b, p));

		return dp[index][b][p];
	}
}