[백준] 1106번 호텔

💡문제접근

• 대표적인 동적 프로그래밍 문제
• 얼마의 cost 비용을 들여 cnt_num만큼의 고객을 창출한다는 표현을 명심

💡코드(메모리 : 31256KB, 시간 : 52ms)

import sys
input = sys.stdin.readline

C, N = map(int, input().strip().split())
lst = [list(map(int, input().strip().split())) for _ in range(N)]
dp = [1e6] * (C+100) # dp[i] : i명의 고객을 확보하기 위해 투자해야하는 돈의 최솟값 테이블
dp[0] = 0

for cost, cnt in lst:
    for i in range(cnt, C+100):
        dp[i] = min(dp[i], dp[i-cnt] + cost)
print(min(dp[C:]))

💡소요시간 : 25m