bj1106 호텔

문제

• 백준 URL: 호텔
• 난이도 골드 4

풀이

import sys

input = sys.stdin.readline
c, n = map(int, input().split())
promos = []
for _ in range(n):
    cost, customer = map(int, input().split())
    promos.append((cost, customer))

dp = [float('inf')] * (c + 101)
dp[0] = 0

for cost, customer in promos:
    for i in range(customer, c + 101):
        if dp[i - customer] != float('inf'):
            dp[i] = min(dp[i], dp[i - customer] + cost)

result = min(dp[c:])

print(result)

풀이 방법은 다음과 같다.
1. DP 테이블을 초기화한다. 한번에 홍보로 얻을 수 있는 사람 수가 100명이기 때문에 c+101(100명 + 인덱싱으로 인한 1)로 크기를 잡아준다. 0명을 모으는데는 0원이 들기 때문에 dp[0]=0이다.
2. 2중 for문을 통해 dp 테이블을 채워나간다.
1. 바깥쪽 루프에서는 각 홍보 방안(cost, customer)을 순회한다.
2. 안쪽 루프에서는 customer 명부터 c+100 명까지 고객 수를 늘려가며 dp 값을 갱신한다.
3. 핵심 점화식은 다음과 같다.
1. if dp[i - customer] != float('inf'): 이는 (i-customer)명을 모으는 방법이 존재할 때만 갱신하기 위함이다.
2. dp[i] = min(dp[i], dp[i - customer] + cost)에서 dp[i]는 현재까지 알려진 i명을 모으는 최소 비용이다. dp[i - customer] + cost는 (i - customer)명을 모은 상태에서, 현재 홍보 방안을 추가해 i명을 만드는 데 드는 비용이다. 이 둘을 비교해 더 작은 값으로 dp[i]를 갱신한다.