[Python/파이썬] 백준 17208번 카우버거 알바생

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

코드

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
orders = []
for _ in range(n):
    x, y = map(int, input().split())
    orders.append((x, y))

dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]
answer = 0
for order_idx in range(1, n+1):
    now_burger, now_fry = orders[order_idx-1]
    for burger in range(m+1):
        for fry in range(k+1):
            if burger+now_burger <= m and fry+now_fry <= k:
                dp[order_idx][burger][fry] = max(
                    dp[order_idx-1][burger+now_burger][fry+now_fry]+1, dp[order_idx-1][burger][fry])
            else:
                dp[order_idx][burger][fry] = dp[order_idx-1][burger][fry]
            if answer < dp[order_idx][burger][fry]:
                answer = dp[order_idx][burger][fry]
print(answer)

이 문제는 0-1 Knapsack 문제로 DP를 사용하여 풀 수 있다.

 

DP[i][j][k]는 i번째 주문까지 고려했을 때, 버거가 j개, 후라이가 k개일 때 처리된 최대 주문 수를 저장한다. 점화식은 다음과 같다.

 

처음에는 아래와 같이 백트래킹으로 풀었는데, 시간 초과가 발생했다.

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
orders = []
for _ in range(n):
    x, y = map(int, input().split())
    orders.append((x, y))
answer = 0


def knapsack(idx, remain_burger, remain_fry, ordered):
    global answer
    if idx == len(orders):
        answer = max(answer, ordered)
        return
    if len(orders)-idx+ordered <= answer:
        return
    if remain_burger >= orders[idx][0] and remain_fry >= orders[idx][1]:
        knapsack(idx+1, remain_burger -
                 orders[idx][0], remain_fry-orders[idx][1], ordered+1)
    knapsack(idx+1, remain_burger, remain_fry, ordered)


knapsack(0, m, k, 0)
print(answer)

이 풀이의 문제점은 시간 복잡도가 O(2^N)이기 때문에 N이 100일 때 최대 2^100번의 연산을 해야 하기 때문에 시간 초과가 발생한 것으로 보인다.

DP로 변경된 풀이는 시간 복잡도가 `O(n·m·k)`이기 때문에 knapsack으로 풀이할 때보다 시간을 많이 줄일 수 있다.