[백준 문제풀이] 얼렁뚱땅 1106 호텔 풀이

얼렁뚱땅 백준 문제풀이

[백준 문제풀이] 얼렁뚱땅 1106 호텔 풀이

MOSTAR 2022. 10. 22. 16:11

https://www.acmicpc.net/problem/1106

1106번: 호텔

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때

www.acmicpc.net

c, city = map(int,input().split())

# idx 0 : cost, idx 1 : customer_num 
arr = [list(map(int,input().split())) for _ in range(city)]
c_list = [10**6] * (c+101)
c_list[0] = 0

arr.sort(key=lambda x:x[0])

for cost, cus in arr :
    for i in range(cus,c+100) :
        c_list[i] = min(c_list[i-cus] + cost, c_list[i])

print(min(c_list[c:]))

dp 어려워 어려워 어려워어려워 아이디어 생각안나안나안나아난안아나낭나아안아난아나아나안아나아나아난아나아나