호텔 ( 1106 번 )

1106번: 호텔

 

🧠 알고리즘

특정 고객 수 이상을 유치하기 위한 최소 비용을 구하는 문제.
동적 계획법(DP)을 이용해 각 고객 수마다 최소 비용을 누적 계산하며
광고를 여러 번 사용할 수 있으므로 무한 배낭(Unbounded Knapsack) 방식으로 접근.

 

🧾 코드

import sys

def _main(c, max_cs_ct, cs):
    answer = float('inf')
    dp = [float('inf')] * (c + max_cs_ct + 1)
    dp[0] = 0

    for cost, count in cs:
        for idx in range(count, len(dp)):
            dp[idx] = min(dp[idx], dp[idx - count] + cost)
            if idx >= c:
                answer = min(answer, dp[idx])

    return answer

c, n = map(int, sys.stdin.readline().rstrip().split())
cs, max_cs_ct = [], 0
for _ in range(n):
    a = tuple(map(int, sys.stdin.readline().rstrip().split()))
    max_cs_ct = max(max_cs_ct, a[1])
    cs.append(a)

print(_main(c, max_cs_ct, cs))

 

⏱️ 시간 복잡도

for cost, count in cs : # 반복 n번 ( 선형 시간 )
    for idx in range(count, len(dp)): # 반복 ( 선형 시간 )
    
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )