[Python] 1106 - 호텔

[Gold IV] 호텔 - 1106 

[문제 링크](https://www.acmicpc.net/problem/1106)

🗝️알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

---

💻문제 정의

c원으로 p명의 고객을 늘릴 수 있다고 할 때, c와 p가 주어지고, 최소 C명 이상 호텔의 고객을 늘리기 위해 투자해야 하는 돈의 최솟값을 구하는 문제이다.

 

💡접근 및 설계

기존의 널리 알려진 방법인 베낭 문제(Knapsac)과 다이나믹 프로그래밍(DP)를 활용하여 문제를 해결하였다.

 

✏️알고리즘 풀이

dp = [INF] * (C+100)
dp[0] = 0 # 0명일때 비용은 0원

for cost, person in hotel:
    for i in range(person, C+100):
        dp[i] = min(dp[i-person] + cost, dp[i]) # 현재의 비용과 인원 추가 전의 비용을 비교하여 작은 비용을 저장

dp리스트의 인덱스는 인원 수이고, dp리스트의 값은 해당 인덱스인 인원을 늘리기 위한 최소 비용이다.

 

인원을 추가하기 이전의 비용과 현재의 인원을 추가한 비용의 합과, 이미 저장되어 있는 비용을 비교하여 더 적은 값으로 업데이트하여 진행한다.

 

또한, 적어도 C명 이상을 모집하였을 때의 최소 비용이기 때문에, C명 이상의 경우에서 C명일때보다 적은 비용이 발생할 수도 있다.

이 경우 최대 비용은 100원이기 때문에 C+100까지 반복을 진행한다.

 

🗒️제출 코드

# 1106 호텔

C, N = map(int, input().split())

INF = 1_000_000_000

hotel = []
dp = [INF] * (C+100)
dp[0] = 0 # 0명일때 비용은 0원

for _ in range(N):
    cost, person = map(int, input().split())
    hotel.append([cost, person])

for cost, person in hotel:
    for i in range(person, C+100):
        dp[i] = min(dp[i-person] + cost, dp[i]) # 현재의 비용과 인원 추가 전의 비용을 비교하여 작은 비용을 저장

print(min(dp[C:]))

---