[BOJ] 백준 17208번 문제 풀이 (Python)

1. 풀이

들어온 카우버거 주문 중 남아있는 치즈버거와 감자튀김으로 총 몇 개의 주문을 최대한 처리할 수 있는지에 관한 문제였다. 일종의 knapsack problem(배낭채우기 문제)으로 완전탐색으로 풀 수 있는 코드를 먼저 만든 이후 memoization을 방식을 추가하면되는 비교적 간단한 형식의 dynamic programming 문제였다.

knapsack problem은 백준 온라인 저지 기준 dynamic programming 분야에서 골드 난이도에 많이 출제되는 문제이다. 보통 다음과 같은 조건이면 knapsack problem으로 보면 된다.

• 주어진 입력들을 하나씩 포함/미포함 하면서 결과를 내는 문제
  • 배낭채우기 문제의 경우 각 물건을 포함/미포함 하면서 결과를 만들어낸다.
• 정해진 조건(배낭 채우기의 경우, 가방의 무게)내에서 최대의 결과(배낭 채우기의 경우, 가격)를 판단하는 문제

knapsack problem의 경우 먼저 재귀함수를 이용한 완전 탐색 코드를 먼저 구성한 뒤 memoization을 적용하는 방식을 추천한다. 이 방식이 익숙해진다면 나중에 어떤 재귀함수를 구성했을 때 memoization을 이용해 시간을 단축시킬 수도 있을 것이다.

완전 탐색

def solve(idx, burger, fry):
    if idx == n: return 0
    ret = 0
    if burger >= order_list[idx][0] and fry >= order_list[idx][1]:
        ret = 1 + solve(idx+1,burger - order_list[idx][0], fry - order_list[idx][1])
    ret = max(ret, solve(idx+1,burger, fry))
    return ret

Dynamic programming 변형

def solve(idx, burger,fry):
    if idx == n: return 0
    if dp[idx][burger][fry] != -1: return dp[idx][burger][fry]
    dp[idx][burger][fry] = 0
    if burger >= order_list[idx][0] and fry >= order_list[idx][1]:
        dp[idx][burger][fry] = 1 + solve(idx+1,burger - order_list[idx][0], fry - order_list[idx][1])
    dp[idx][burger][fry] = max(dp[idx][burger][fry], solve(idx+1,burger,fry))
    return dp[idx][burger][fry]

전체 코드

import sys
def input(): return sys.stdin.readline().rstrip()

def solve(idx, burger,fry):
    if idx == n: return 0
    if dp[idx][burger][fry] != -1: return dp[idx][burger][fry]
    dp[idx][burger][fry] = 0
    if burger >= order_list[idx][0] and fry >= order_list[idx][1]:
        dp[idx][burger][fry] = 1 + solve(idx+1,burger - order_list[idx][0], fry - order_list[idx][1])
    dp[idx][burger][fry] = max(dp[idx][burger][fry], solve(idx+1,burger,fry))
    return dp[idx][burger][fry]

n,m,k = map(int, input().split())
order_list = [tuple(map(int,input().split())) for _ in range(n)]

dp = [[[-1] * (k+1) for _ in range(m+1)] for _ in range(n)]

print(solve(0,m,k))