[백준/파이썬] #1106

DP의 식은 근접했으나, for문을 어떻게 돌릴지에 대해서 더 생각해볼 필요가 있는 문제였다. 

바로 아래는 시도했으나 테스트 케이스만 맞고 나머지에서 틀린 풀이이고, 다른 풀이를 참조해서 맨 아래와 같이 풀어보았다. 

C, N = map(int, input().split())

DP = [1e9] * (C+1)
prices = [0] * N
customers = [0] * N

DP[0] = 0

for i in range(N):
    price, customer = map(int, input().split())
    prices[i] = price
    customers[i] = customer

min_price = min(prices)
for i in range(1, C+1):
    if i < min_price:
        continue
    for j in range(N):
        current_price, current_customer = prices[j], customers[j]
        current_index = max(i-current_customer, 0)
        DP[i] = min(DP[i], DP[current_index] + current_price)

print(DP[C])

C, N = map(int, input().split())

DP = [1e9] * (C+100)
prices = [0] * N
customers = [0] * N

DP[0] = 0

for i in range(N):
    price, customer = map(int, input().split())
    prices[i] = price
    customers[i] = customer

for i in range(N):
    price, customer = prices[i], customers[i]
    for j in range(customer, C+100):
        DP[j] = min(DP[j], DP[j-customer] + price)

print(min(DP[C:]))