BOJ 1106 호텔

문제

접근 방법

사실 input 범위를 보고 DP라는 것을 예상했다. dp[i]를 비용 i로 얻을 수 있는 최대 고객 수라고 설정하고 비용 0부터 가능한 홍보 비용을 더해서 최대 고객 수를 얻으면 된다는 생각을 하였다.

이때, 동일한 비용으로 다른 홍보 효과를 낼 수 있는 입력이 존재한다는 생각을 바로 하지 못했다… 조금 더 예외 상황을 잘 판단하는 습관을 길러야겠다.

정답 코드

import sys
input = sys.stdin.readline

c,n = map(int, input().split())

costs = []
ppl = []
for _ in range(n):
  cost, p = map(int, input().split())
  costs.append(cost)
  ppl.append(p)

#dp[i]는 i의 비용으로 얻을 수 있는 최대 고객
max_cost = 1000*100
dp = [0]*(max_cost+5)

for cost,p in zip(costs, ppl):
  dp[cost] = max(dp[cost], p)

for i in range(max_cost+5):
  for cost,p in zip(costs, ppl):
    if i+cost <= max_cost+4:
      dp[i+cost] = max(dp[i+cost], dp[i] + p)

for i in range(max_cost+5):
  if dp[i] >= c:
    print(i)
    break