백준 17208 카우버거 알바생

 

17208번: 카우버거 알바생

문제

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

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

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

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

 

풀이

냅색 문제이다.

 

예제 입력 1

4 3 4

2 5

1 2

3 3

2 1

이 경우, 주문의 수는 4개 주방에 남은 치즈버거는 3개, 주방에 남은 감자튀김 개수는 4개이다.

차례대로 주문이 들어오면 그 주문을 처리할 수도, 처리하지 않을 수도 있다.

첫 번째 주문(주문번호 0)을 처리 할 경우,

치즈버거 2개 감자튀김 5개이므로 남은 감자튀김보다 주문량이 더 많기 때문에 처리할 수 없다.

따라서 이 주문은 처리할 수 없다.

이 상황을 그림으로 그려보자면 아래와 같다. 

0은 주문 번호,3은 남은 치즈버거,4는 남은 감자튀김이다. (주문번호는 0번부터 시작한다)

 

두 번째 주문은 1 2 (주문번호 1) 이므로

주문을 처리할 수 있다. 만약 주문을 처리하지 않는다면 치즈버거와 감자튀김의 수는 그대로이다.

3번째 주문의 상황을 그리면 아래와 같다.

재귀를 활용해

이렇게 가지를 치면서(?) 경우마다 가장 많이 주문을 받을 수 있는 경우를 저장하고 반환 하면된다.

예를들어 2,3,4 의 경우 최고의 주문수는 3,0,1 의 경우에서 + 1을 한것과 3,3,4의 경우 중에 더 큰 것이다.

핵심 코드는 아래이다.

1. 더 이상 주문이 없으면 0을 반환한다.(주문번호 pos가 N일때, 주문번호는 0~N-1까지 있다.)

2. 남아있는 치즈버거랑 감자튀김이 주문량보다 많으면 주문을 처리할 수 있으므로 ret에 저장한다.

3. 주문을 처리하지 않는 경우와 비교해서 큰 값을 반환한다. ( 치즈버거랑 감자튀김이 주문량보다 작은 경우는 주문을 처리하는 경우는 없다)

int knapsack(int pos, int c, int f)
{
    if (pos == N) return 0;
    int ret = 0;
    if (cheese[pos] <= c && ff[pos] <= f) {
        ret = knapsack(pos + 1, c - cheese[pos], f - ff[pos]) + 1;
    }
    ret = max(ret, knapsack(pos + 1, c, f));
    return ret;
}

이대로 실행하면 많은 중복연산을 하게되므로 시간초과가 날 수 있어서

메모이제이션을 해줘야한다.

dp[주문번호][남은 치즈버거][남은 감자튀김] 이렇게 배열을 만든다.

처음 dp배열을 -1로 초기화해준 다음(계산이 되지 않은 상태)

계산이 되면 dp값을 갱신해 준 뒤, 또 호출이 된다면 그 값을 반환해준다.(중복 연산을 할 필요없다.)

예를들어 knapsack(2,3,4)를 이미 실행한뒤,  다른 가지(?)에서 또 knapsack(2,3,4)를 실행한다면 knapsack(3,0,1) 함수도 또 실행되고, knapsack(3,3,4) 함수도 또 실행되고 그 함수도 또 다른 함수를 실행하고.. 이런 경우를 만들지 않는것이다.

이런식으로 코드를 작성하면 된다.

int dp[MAX][301][301];
 
int knapsack(int pos, int c, int f)
{
    if (pos == N) return 0;
    if (dp[pos][c][f] >= 0) return dp[pos][c][f];
    int ret = 0;
    if (cheese[pos] <= c && ff[pos] <= f) {
        ret = knapsack(pos + 1, c - cheese[pos], f - ff[pos]) + 1;
    }
    ret = max(ret, knapsack(pos + 1, c, f));
    return dp[pos][c][f] = ret;
}

아래는 정답을 받은 소스코드이다.

#include <iostream>
#include <algorithm>
#define MAX 101
 
using namespace std;
 
int N;    // N: 주문의 수
int M, K;    // M: 치즈버거 개수, K: 감자튀김 개수
int cheese[MAX];    // 치즈버거 주문
int ff[MAX];        // 감자튀김 주문
int dp[MAX][301][301];
 
int knapsack(int pos, int c, int f)    
{
    if (pos == N) return 0;    // 주문할게 없으면 0을 반환
    if (dp[pos][c][f] >= 0) return dp[pos][c][f];    // 이미 계산된 값
    int ret = 0;
    if (cheese[pos] <= c && ff[pos] <= f) {
        ret = knapsack(pos + 1, c - cheese[pos], f - ff[pos]) + 1;    // 주문을 처리할 수 있음
    }
    ret = max(ret, knapsack(pos + 1, c, f));    
    return dp[pos][c][f] = ret;    // dp값을 갱신함과 동시에 결과값 반환
}
 
int main(void)
{
    cin >> N >> M >> K;    // N: 주문의 수, M: 치즈버거 개수, K: 감자튀김 개수
    
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= M; ++j) {
            for (int k = 0; k <= K; ++k) {
                dp[i][j][k] = -1;    // dp값 초기화
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        cin >> cheese[i] >> ff[i];    // 주문
    }
 
    cout << knapsack(0, M, K) << "\n";
 
    return 0;
}