[백준] 1106번 : 호텔

1106번: 호텔

1106번: 호텔

📄 문제개요

• 형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보를 하는데 드는 비용과, 그 때 몇명의 호텔 고객이 늘어나는지에 대한 정보가 있다.
• 단, 9원들 들여서 홍보하면 고객이 3명 늘어나는 조건에서 → 3원을 들여서 1명의 고객, 12원을 들려서 4명의 고객을 늘어나게 할수 없다. (9원 3명, 18원 6명, 27원 9명) 가능
• 호텔에 고객을 적어도 C명 늘리기 위해, 형택이가 투자해야 하는 돈의 최소값을 구하는 프로그램을 작성하시오.
• 정보 ( 비용, 고객수 )

🤔 문제분석

• 예외사항 생각해보기
  • 예를들어 C가 5이고, 정보가 (1, 2), (10 ,5)가 주어진다면, 6명을 선택하고 비용이 3인 결과를 출력해야한다.
• 고객의 명수는 20 * 100 인 최대 2000 까지 갖을 수 있다. 1000부터, 2000까지 중 최소값을 출력하면 된다.
• 비용은 최대 2000보다 작은 자연수이다.
• 정보로부터, 비용이가장 작은 값부터 순회하면서 바텀업 방식으로 고객의 명수를 대상으로 비용을 초기화 한다.
• 고객의 명수로부터 시작해서 2000까지 비용을 증가시키면서 최소값을 갱신한다.
• 예를들어 고객의 명수가3 , 비용이 5일경우를 생각해보자.
  • i가 1부터 시작해서 , 1씩 증가할때, (명수*i)는 2000보다 작거나 같다.
  • dp[(명수i)] = min(dp[(명수i)], dp[(명수*i) -3] + 비용)
  • dp[(명수i)] = min(dp[(명수i)], dp[(명수*i)-3] + 비용)
  • dp[(명수i)] = min(dp[(명수i)], dp[(명수*i)-3] + 비용)
  • dp[(명수i)] = min(dp[(명수i)], dp[(명수*i)-3] + 비용)

📝 의사코드

• 정보를 비용을 내림차순으로 정렬한다.
• 정보를 순회하면서 정보를 위의 아래 점화식과 같이 채워나간다.
  1. 고객의 명수가 n, 비용이, c 이라고 했을때 i = 1 로 시작한다., n*i은 2000보다 작거나 같을때까지 반복한다.
  2. dp[ni] = min(dp[ni], dp[n*i - n] + c)

💻 코드

import sys
input = sys.stdin.readline
INF = int(1e9)

C, N = map(int, input().split())
info = []

for _ in range(N):
    c, n = map(int, input().split())
    info.append((c, n))

# 명수가 가장 크면서, 비용이 작은것부터 채운다.
info.sort(key=lambda x:(-x[1], x[0]))
dp = [INF for _ in range(2001)]
dp[0] = 0

for c, n in info:
    i = 1
    while 2000 >= i:
        if i - n >= 0:
            dp[i] = min(dp[i], dp[i - n] + c)
        i += 1

print(min(dp[C:]))

🎯 피드백 및 개선사항

• 점화식을 잘 못 세웠습니다.

1. dp[ni] = min(dp[ni], dp[n*i - n] + c)가 명수가 배수대로 증가하는 것이 아니라,
2. 1. dp[i] = min(dp[i], dp[i - n] + c) 이전에 있던 값중에서 최소값을 갱신해주어야 합니다.

❓다른사람은 어떻게 풀었을까?

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

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

2중 for문을 활용하여 문제를 해결하였습니다. 원리는 똑같습니다.

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:]))