[BOJ]17208. 카우버거알바생 (python)

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는 감자튀김 요구 개수를 나타낸다.

출력

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

 

풀이

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

12865번: 평범한 배낭

이 문제와 거의 동일하다. 다만 확인할 조건이 2개가 됐을 뿐이다!!

핵심은 dp를 어떻게 저장해 나갈 것인가이다.
예를 들어, 현재 3개의 햄버거와 4개의 후라이가 있을 때, 각각 1, 2개를 필요하는 주문이 들어왔다면

이 주문을 해결한 후, 2개의 햄버거와 2개의 후라이로 처리할 수 있는 주문의 수와
이 주문을 해결하지 않고 3개의 햄버거와 4개의 후라이로 처리할 수 있는 주문의 수 중
큰 값을 선택하는 로직이다!!

즉, z축은 가능한 주문의 종류(0 ~ order_N) x, y축은 현재 가진 음식의 양이다
따라서    dp[i][bur][fri] = max(1 + dp[i - 1][bur - burger][fri - fries], dp[i - 1][bur][fri]) 로 정리할 수 있다.
(자세한건 코드로 보는게 이해하기 좋습니다!)

 

코드

 

 

import sys
read = sys.stdin.readline


order_N, left_burger, left_fries = map(int, read().strip().split())
order_list = [[0, 0]] + [list(map(int, read().strip().split())) for _ in range(order_N)]

# 주문의 개수가 i개이고, 남은 버거는 bur, 남은 후라이는 fri일 때 처리할 수 있는 최대 주문의 수를 담는 dp배열
dp = [[[0] * (left_fries + 1) for _ in range(left_burger + 1)] for _ in range(order_N + 1)]


for i in range(1, len(order_list)):
    burger, fries = order_list[i]
# 현재 가진 햄버거와 후라이의 개수, 즉 bur / fri 가 요구량보다 넉넉하다면, 그 양을 뺐을 때 처리할 수 있는 주문의 수 + 1을 해준다.
    for bur in range(1, left_burger + 1):
        for fri in range(1, left_fries + 1):
            if burger <= bur and fries <= fri:
                dp[i][bur][fri] = max(1 + dp[i - 1][bur - burger][fri - fries], dp[i - 1][bur][fri])
            else:
                dp[i][bur][fri] = dp[i - 1][bur][fri]

answer = []
for i in dp:
    temp = list(map(max, i))
    answer.append(max(temp))
print(max(answer))


# print(dp[order_N][left_burger][left_fries]) 이렇게 출력하는게 더 효율적일듯!