[백준] 1106 - 호텔 🏨 (Python) / 골드 5 / DP

BAEKJOON Logo

C,N = map(int,input().split())
cost_list = [list(map(int,input().split())) for _ in range(N)]
dp = [1e7 for _ in range(C+100)]
dp[0]=0

for cost, num_people in cost_list:
    for i in range(num_people,C+100):
        dp[i] = min(dp[i-num_people]+cost,dp[i])

print(min(dp[C:]))

 

Contents

 

---

1.  문제🔥

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

문제

문제를 요약하자면, 얻어야 하는 고객 명수 C와 도시 개수 N이 주어질 때, 다음 N개의 줄에는 각 도시에서 홍보할 때 드는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어집니다. 호텔의 고객을 최소 C명 늘이기 위해 투자해야 하는 돈의 최솟값을 출력해야 합니다.

 

1) 예제 입출력❄️

예제 입출력

12명을 확보해야 하고, 도시는 2개입니다. 각 도시별로 3원에 5명, 1원에 1명을 확보할 수 있습니다. 그러면 3원씩 2번, 1원씩 2번 쓰면 12명을 확보할 수 있습니다. 그래서 3+3+1+1 해서 8원이 정답입니다.

2. 핵심 논리☢️

각 인덱스를 확보해야 하는 고객 수로 하고, 그 고객을 확보하는 데 사용되는 최소 비용을 값으로 하는 dp 리스트를 만드는 게 핵심입니다. 입력받은 각 비용과 확보 가능한 고객 수를 반복하며 dp를 갱신해 나가야 합니다.

 

3. 풀이 코드✅

1) 코드

C,N = map(int,input().split())
cost_list = [list(map(int,input().split())) for _ in range(N)]
dp = [1e7 for _ in range(C+100)]
dp[0]=0

for cost, num_people in cost_list:
    for i in range(num_people,C+100):
        dp[i] = min(dp[i-num_people]+cost,dp[i])

print(min(dp[C:]))

얻어야 하는 고객 명수 C와 도시개수 N을 입력받습니다. N번 반복하며 비용과 확보 가능한 고객 수로 cost_list를 입력받습니다. dp 리스트를 매우 큰 값(1e7)으로 C+100개만큼 초기화해 줍니다. C+100으로 하는 이유는 dp에서 C명에 대한 최소비용을 출력할 때, C명보다 많은 고객 수에서 최소비용이 나올 수 도 있기 때문입니다. 그리고 그 수를 100으로 한 이유는 주어지는 비용은 최대 100원을 넘지 않기 때문입니다. 예를 들어, C가 3이고, dp를 채운 결과 3명에 대한 최소비용이 3원인데, 4명을 구할 때 1원인 도시가 있다면 이 때는 3원이 아니라, 1원을 출력해야 합니다. 

 그리고 비용(cost)와 확보 가능한 고객 수(num_people)를 for문으로 반복하며 num_people부터 C+100까지 돌며 dp 리스트를 갱신합니다. 이때, 핵심 코드는 dp[i] = min(dp[i-num_people]+cost, dp[i])입니다. 이 코드의 의미는 현재 i명을 모집할 때, cost의 도시에 대한 비용(dp[i-num_people]+cost)과 과거까지 i명을 확보하는데 계산된 최소비용(dp[i])중에 최솟값으로 갱신하겠다는 의미입니다.

그렇게 dp를 모두 갱신했으면 dp[C]를 출력하는 게 아니라 min(dp[C:])를 출력합니다. 이는 C명일 때 최소 비용보다 C명 보다 더 많은 고객에 대한 최소비용이 더 작을 수 있기 때문입니다.

 

2) 주석달린 코드

C,N = map(int,input().split()) # 늘려야하는 고객수 C와 홍보할 수 있는 도시개수 N
cost_list = [list(map(int,input().split())) for _ in range(N)] # 비용과 비용으로 얻을 수 있는 고객수
dp = [1e7 for _ in range(C+100)] # dp 리스트 매우 큰값으로 초기화
dp[0]=0 # 0명 모을 땐, 0원

for cost, num_people in cost_list: # 각 비용, 비용으로 얻을 수 있는 고객수에 대해
    for i in range(num_people,C+100): # num_people 부터 C+100 까지 반복
        dp[i] = min(dp[i-num_people]+cost, dp[i]) # i명일 때, 최소비용 갱신

print(min(dp[C:]))

 

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/1106_%ED%98%B8%ED%85%94.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

 

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/