[백준] 1106 호텔 [Python]

 

위 문제는 원하는 인원수를 최소 비용으로 구하는 방법을 요구하는 문제입니다.  

 

제 풀이는 다이내믹 프로그래밍을 사용해서 풀었고 이 문제를 구현할 때는 "이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오." 문장을 잘 확인해야 합니다.

 

예제 2번같은 경우를 보면 dp [10]을 구해야 하지만 dp [3]=1 , dp [6]=2, dp [9]=3이 될 때 dp [10]은 4로 구해지는 것을 봤을 때 뒤에 부분까지 구하고 최솟값을 구한다고 생각하면 됩니다.

 

따라서 범위는 구하고자하는 C의 범위에 배열 arr의 최대 인원값을 더해준 범위까지 구한 것의 최솟값을 구하면 됩니다.

 

전체 코드

from sys import stdin as s
s=open('input.txt','rt')

C,N = map(int,s.readline().split())
arr=[]
count=0
for i in range(N):
    cost,people = map(int,s.readline().split())
    arr.append((cost,people))

for i in range(len(arr)):
    count = max(count,arr[i][1])


dp = [1e9] * (C+count + 1)
dp[0]=0

for cost,people in arr:
    for i in range(people,C+count+1):
        dp[i]=min(dp[i-people]+cost,dp[i])

print(min(dp[C:]))

 

처음에 비용과 인원을 입력받고 난 후 arr배열에 저장합니다. 그리고 C값에 최대 인원수를 더해줘야 하므로 최대 인원값인 count를 구합니다.

그다음은 동전, 백팩 문제들과 같은 방법으로 dp를 구해줍니다.

이렇게 진행하면 C부터 초과범위까지 사이에서 최솟값을 구해주면 이 문제의 해답을 찾을 수 있습니다.