[백준] 17208: 카우버거 알바생 - JAVA

https://www.acmicpc.net/problem/17208

 

풀이

버거와 감자튀김을 조합하여 최대한 많은 주문을 처리하는 것이 목표이다.

 

dp를 사용하여 해결했다. 주문을 처리하는 동안 남은 버거와 감튀의 수량을 고려하여 최대 주문 수량을 계산하는 배낭문제였다.

 

현재 주문을 포함하지 않는 경우 dp[i][j][k] = dp[i - 1][j][k],

 

현재 주문을 포함하는 경우 dp[i][j][k] = dp[i - 1][j - order[i][0]][k - order[i][1]] + 1 와 같은 점화식으로 처리했다.

 

---

 

메모리: 52300KB
시간: 232ms
언어: Java 11

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int burgers = Integer.parseInt(st.nextToken());
        int fries = Integer.parseInt(st.nextToken());

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

        int[][][] dp = new int[n + 1][burgers + 1][fries + 1];
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < burgers + 1; j++) {
                for (int k = 1; k < fries + 1; k++) {
                    if (order[i][0] > j || order[i][1] > k) {
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - order[i][0]][k - order[i][1]] + 1);
                    }
                }
            }
        }

        System.out.println(dp[n][burgers][fries]);
    }

}