📙[Algo] BOJ17208. 카우버거 알바생

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

문제 요약

• 주방에 남은 치즈버거와 감자튀김으로 주문을 처리하려고 한다
• 모든 주문은 각각 치즈버거 요구 개수와 감자튀김 요구 개수를 의미하는 2개의 정수로 이루어진다
• 주문이 들어온 순서와 관계없이 원하는 주문을 선택해 처리할 수 있다
• 최선의 방법으로 주문을 선택해 처리한다면 최대 몇 개의 주문을 처리할 수 있을까

시간 제한

• 3초

입력

• 첫째 줄에 주문의 수 N(1 ≤ N ≤ 100), 주방에 남은 치즈버거 개수 M(1 ≤ M ≤ 300), 주방에 남은 감자튀김 개수 K(1 ≤ K ≤ 300)가 주어진다
• 둘째 줄부터 N개의 줄에는 주문 내용을 의미하는 두 정수 x, y (1 ≤ x, y ≤ 300)가 주어진다
  • x는 치즈버거 요구 개수, y는 감자튀김 요구 개수를 나타낸다

출력

• 주방에 남은 치즈버거와 감자튀김을 사용해 처리할 수 있는 최대 주문 개수를 출력

접근법

• 현재 주문을 처리하느냐, 안 하느냐에 따라 치즈버거와 감자튀김의 남은 개수를 갱신하고,
• 만약 치즈버거나 감자튀김이 음수가 나올 경우 해당 케이스는 불가능 한 경우이므로 정답이 될 수 없는 가장 작은 수를 반환했다. ⇒ 가지치기
• 만약 모든 주문을 순회 했다면, 가능한 경우라 판단하여 0을 반환했다.
• 재귀 호출 할때마다
  • 주문을 처리하는 경우에만 1을 더해줬다.
• 메모이제이션을 하지 않을 경우, 처리 하는 경우와 하지 않는 경우 2가지로 나뉘고, 이 경우가 총 N개의 주문에 적용되므로 2 ^ N이 걸리며, 추가로 남은 햄버거와 감자튀김 개수 상태에 따라 여러 케이스로 나뉘므로 M*K*(2^N)이 된다.
  • 주어진 데이터 범위에 따르면 시간초과가 뜨므로, 중복 계산이 되지 않도록 해야해서 메모이제이션을 적용했다. ⇒ N*M*K로 줄어든다.

코드

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

public class Main {
    static int N, M, K;
    static int[][] order;
    static int[][][] dp = new int[110][310][310];

    // 메모이제이션 안 할 경우 시간복잡도 => (2 ^ 100) * 300 *300
    // 메모이제이션 적용 후 => 100 * 300 * 300
    static int dfs(int cur, int burger, int potato) {
        if (burger < 0 || potato < 0) return Integer.MIN_VALUE;
        if (cur == N) return 0;
        if (dp[cur][burger][potato] != -1) return dp[cur][burger][potato];

        int ret = 0;
        // 현재 주문 처리 O
        ret = Math.max(ret, dfs(cur + 1
                , burger - order[cur][0]
                , potato - order[cur][1]) + 1);
        // 현재 주문 처리 X
        ret = Math.max(ret, dfs(cur + 1, burger, potato));
        dp[cur][burger][potato] = ret;
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        order = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            order[i][0] = Integer.parseInt(st.nextToken());
            order[i][1] = Integer.parseInt(st.nextToken());
        }
        for (int[][] d1 : dp) {
            for (int[] d2 : d1) {
                Arrays.fill(d2, -1);
            }
        }

        int ret = dfs(0, M, K);
        System.out.println(ret);
    }
}