[백준 1106 🥇] 호텔

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

1106번: 호텔

문제

세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.

형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.

예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.

각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

문제 풀이

• 특정 비용을 들여서 홍보를 할지 말지를 판단하는 0/1 knapsack 문제이므로 DP를 이용해서 풀었다.
• 주의할 점은 dp의 크기를 단순히 c로 선언하는 것이 아니라, c+100으로 선언해야 한다.  
  • 왜냐하면, c보다 더 많은 사람에 홍보할 수 있는 비용이 c를 홍보하는 비용보다 더 적게 들 수 있기 때문이다.
  • 예를 들어, c명에게 홍보하는 비용이 4원인데, 1원으로 c+1명에게 홍보할 수 있는 정보가 주어지는 경우도 있기 때문이다.
  • c+100으로 잡은 이유는 문제를 읽어보면 홍보할 수 있는 사람의 최대 수가 100이기 때문이다. 
• 먼저 0명에게 홍보할 수 있는 비용은 0원이므로 dp[0]=0을 선언해준다.
• 그리고, info 배열에 저장해둔 비용과 홍보 가능 인원을 for문으로 탐색하면서 for문을 돌면서 현재 탐색 중인 홍보 가능 인원부터 c+100까지 탐색하면서 비용을 사용해서 홍보하는 것과 그 전에 계산한 dp 값 중 더 작은 값으로 dp 값을 갱신해준다.
  • dp[i-people]+cost 
    • 예를 들어 5명에게 홍보하는 데에 3원이 든다고 가정했을 때, dp[6]를 계산해야 한다면 1명에게 홍보하는 최솟값인 dp[1]에서 cost를 추가해서 5명에게 더 홍보할 수 있는 값으로 계산한 dp[6]이 기존의 for문을 돌면서 계산된 dp[6] 값(아직 계산되지 않아 1e9)보다 더 작다면 dp[6-5]+3 값으로 dp[6]을 갱신해주는 것이다.
• 이러한 과정을 모든 info 배열과 각 배열의 홍보 인원 ~ c+100 까지 탐색하고, dp 값의 인덱스가 c 이상인 값들 중 가장 작은 값을 출력하면 된다.

import sys

input=sys.stdin.readline
c,n=map(int, input().split(' '))
# 비용 / 사람 수
info=[list(map(int, input().split(' '))) for _ in range(n)]

# info로 입력 될 수 있는 최대 사람 수가 100명이고, c보다 더 많은 사람에게 홍보할 수 있는 비용이 최솟값일 수 있음
dp=[1e9]*(c+100)
dp[0]=0
for cost, people in info:
    for i in range(people, c+100):
        dp[i]=min(dp[i-people]+cost, dp[i])

print(min(dp[c:]))