[ 백준 / BOJ 17208 ] 카우버거 알바생

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

17208번: 카우버거 알바생

 

문제

---

중간고사 종료를 기념해 계획 없이 돈을 쓰던 영석이는 안타깝게도 통장 잔고가 100원도 남지 않게 되었고, 결국 영석이는 카우버거 주방 알바를 하기로 했다. 카우버거는 치즈버거와 감자튀김을 파는 중앙대학교의 유명한 음식점이다.

알바 첫날, 영석이가 주방에 들어선 순간 그는 매우 중요한 사실을 깨달았다. 사실 그는 치즈버거는 물론이고 감자튀김도 만들 줄 모른다는 것이다. 이때 다행히도 주방에는 누군가 만들어둔 치즈버거와 감자튀김이 몇 개 남아있었고, 영석이는 현재 들어온 주문을 이걸 이용해 처리하기로 했다.

모든 주문은 각각 치즈버거 요구 개수와 감자튀김 요구 개수를 의미하는 2개의 정수로 이루어진다. 어떤 주문을 처리하기 위해서는 치즈버거와 감자튀김을 정확히 그 주문에서 요구하는 만큼 써야 한다. 또한 주문이 들어온 순서와 관계없이 원하는 주문을 선택해 처리할 수 있으며, 한번 처리한 주문은 사라지므로 같은 주문을 다시 처리하는 것은 불가능하다.

아쉽게도 주방에 남아있는 것이 많지 않기 때문에 어떤 주문은 처리하지 못할 수도 있다. 최선의 방법으로 주문을 선택해 처리한다면 최대 몇 개의 주문을 처리할 수 있을까?

 

입력

---

첫째 줄에 주문의 수 N(1 ≤ N ≤ 100), 주방에 남은 치즈버거 개수 M(1 ≤ M ≤ 300), 주방에 남은 감자튀김 개수 K(1 ≤ K ≤ 300)가 주어진다.

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

 

출력

---

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

 

풀이

---

그림으로 그려보면, 

으로 왼쪽 화살표는 선택 ‼️ 오른쪽 화살표는 선택하지 않음‼️ 이다.

 

DP[ M+1 ][ K+1 ][ N+1] 으로 [ 남은 치즈버거 갯수 ][남은 감자튀김 갯수 ][ 주문 번호 ] 이다. 

Top - Down 방식으로 풀었다.

 

다음 주문의 치즈버거와 감자튀김 갯수가 남은 갯수보다 작으면 선택한다. 

int choose = solve( c - cheeseBurger[idx+1] , f - frenchFry[idx+1], idx+1) + 1 ( idx+1 번호 주문을 선택하는 의미 )

int noChoose = solve( c, f, idx+1 ) ( idx + 1 번호 주문을 선택하지 않는 다는 의미 )

 

idx 가 마지막 주문 번호 ( N ) 이 되면 return 0 을 해준다. 이렇게 0 부터 N까지 호출하고, N번 부터 return 해주면서 최댓값을 구한다.

idx에서는 choose와 noChoose 중 큰 값을 선택해주었따!

 

DP 배열을 -1 로 초기화 해준 이유는 if ( DP > -1) return DP; 해주기 위함인데, 

시간초과 때문이다.

코드

---

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

public class Main_BOJ_17209_카우버거알바생 {
    static int[][][] DP;
    static int N, M, K;
    static int[] cheeseBurger;
    static int[] frenchFry;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());
        K = Integer.parseInt(stringTokenizer.nextToken());

        DP = new int[M+1][K+1][N+1];
        cheeseBurger = new int[N+1];
        frenchFry = new int[N+1];

        for(int i = 1 ; i <= N ; i++){
            stringTokenizer = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(stringTokenizer.nextToken());
            int f = Integer.parseInt(stringTokenizer.nextToken());

            cheeseBurger[i] = c;
            frenchFry[i] = f;
        }

        for(int i = 0 ; i < M+1 ; i++){
            for(int j =0 ; j < K+1 ; j++){
                for(int k = 0 ; k < N+1; k++){
                    DP[i][j][k] = -1;
                }
            }
        }

        System.out.println(solve(M, K, 0));

    }
    private static int solve(int c, int f, int idx) {
        if(idx == N)
            return 0;
        // 이 부분이 없으면 시간 초과!
        if(DP[c][f][idx] > -1)
            return DP[c][f][idx];

        int choose = 0;
        int noChoose = 0;
        if(cheeseBurger[idx+1] <= c && frenchFry[idx+1] <= f){
            // idx+1번째 주문 받음
            choose = solve(c-cheeseBurger[idx+1], f-frenchFry[idx+1], idx+1) + 1;
        }       
        // idx+1 번째 주문 안받음
        noChoose = solve(c, f, idx+1);
        DP[c][f][idx] = Math.max(choose, noChoose);
        
        return DP[c][f][idx];
    }
}