[Python/BOJ] 백준 1106 호텔_DP

 

 

문제에서 적어도 c명을 늘리는 것이므로 더 많이 늘리는 것도 생각을 해주어야 하기 때문에 dp의 크기를 c+100으로 한다. 100의 이유는 100명보다 작거나 같게만 고객의 수가 비용에 따라 증가할 수 있기 때문이다.

 

입력받은 (비용과 고객의 수)리스트를 돈다. (첫번째 for문)
입력받은 고객의 수에서 시작해서 dp리스트의 끝까지 돈다. (두번째 for문)
최소 고객의 수보다 작게는 증가를 못시키기 때문이다. 

 

 

dp[i]의 의미는 i 명을 증가시키는데 필요한 돈의 최솟값이다. 

점화식 : dp[i] = min(dp[i-custo] + cost , dp[i])

 

 

고객을 custo 만큼 늘린 대신 cost를 더한 값과 원래 값중에서 더 저렴한 값으로 갱신한다.

i가 원했던 고객의 수 보다 크보다 같은 경우 값을 갱신한다.

 

 

 

 

 

코드 : 

if __name__=="__main__" :
    c,n = map(int,input().split())
    arr = [list(map(int,input().split())) for _ in range(n)]
    ans  = int(1e9)
    dp = [int(1e9)]*(c+100)
    dp[0] = 0
    for cost,custo in arr :
        for i in range(custo,len(dp)) :
            dp[i] = min(dp[i-custo]+cost,dp[i])
            if i >=c : ans = min(ans,dp[i])
    print(ans)