1106 호텔

문제 분석

문제: https://www.acmicpc.net/problem/1106

이번에는 냅색의 응용 문제를 하나 풀어 보겠습니다. 문제를 읽어보면, 0-1 냅색 상황에 해당한다는 것 자체는 알 수 있습니다.

이번 문제의 특이 사항은 다음과 같습니다.

1. 비용을 최소화 해야 합니다. 그러면서 사람 수를 증가 시켜야 합니다.

2. 그렇게해서 최소화된 비용을 구해야 합니다.

3. 따라서, 용량 제한을 고려하면서 점화식을 세웠던 상황과는 다르게, 비용이 항상 최소화 된 경우라고 생각하고 점화식을 세우면 됩니다. 냅색의 아이디어를 빌려서 다음과 같이 세울 수 있습니다.

   dp[i] : i 명까지 늘렸을 때 필요한 최소 비용
   dp[i] = min(dp[i], *[dp[i - people[j]] + costs[j] for j in range(n)])
dp[0]은 0 입니다. 나머지는 점화식의 성립을 위해 sys.maxsize 로 놓겠습니다.

   점화식이 이해 안가시면 이 글의 그림을 보시면 왜 DP 인지 이해하실 수 있으실 겁니다.

4. 적어도 C 명 늘이기 위해 : 즉, C명까지만 보면 되는 것이 아니라, C에서 최대로 증가 가능한, C + 99 명까지 봐야 합니다.

잘못된 코드 1.

# 호텔

from sys import stdin, maxsize


def read():
    return stdin.readline().rstrip()


c, n = map(int, read().split())
dp = [maxsize for _ in range(c + 100)]
dp[0] = 0

costs = list()
people = list()

for _ in range(n):
    cost, person = map(int, read().split())
    costs.append(cost)
    people.append(person)

for idx in range(1, c + 100):
    for jdx in range(0, n):
        if idx > people[jdx]:
            dp[idx] = min(dp[idx - people[jdx]] + costs[jdx], dp[idx])
        else:
            dp[idx] = dp[idx]

print(min(dp[c:]))

매우 사소하지만 중요한 실수를 하나 저질렀습니다. 어디일까요?

올바른 풀이

# 호텔

from sys import stdin, maxsize


def read():
    return stdin.readline().rstrip()


c, n = map(int, read().split())
dp = [maxsize for _ in range(c + 100)]
dp[0] = 0

costs = list()
people = list()

for _ in range(n):
    cost, person = map(int, read().split())
    costs.append(cost)
    people.append(person)

for idx in range(1, c + 100):
    for jdx in range(0, n):
        if idx >= people[jdx]: # 등호를 빼먹었습니다.
            dp[idx] = min(dp[idx - people[jdx]] + costs[jdx], dp[idx])

print(min(dp[c:]))