난이도

Gold 5

문제

세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.

형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.

예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.

각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

12 2
3 5
1 1

예제 출력

8

해설

배낭 문제와 거의 동일하다. 나는 탑-다운 방식 다이나믹 프로그래밍 방식으로 풀이하면서 순회했다. recursion limit이나 메모리 관련 문제가 발생할 줄 알았는데 그렇지 않아서 다행이다. 코드를 작성하면서 막힘이 없었고, 단번에 정답 판정을 받아 어느정도 기초적인 DP는 이해하게 된 것 같아 뿌듯했다.

제출 코드

import sys
c, n = map(int,sys.stdin.readline().strip().split())
city = []
for i in range(n):
    cost, value = map(int,sys.stdin.readline().strip().split())
    city.append([cost, value])

memo = [0 for i in range(c+1)]
def dfs(num): #num만큼 고객 수를 유치하는 데 최소 비용을 리턴
    if(num <= 0):
        return 0
    if(memo[num] != 0):
        return memo[num]
    else:
        tmpLst = []
        for i in city:
            tmpLst.append(i[0]+dfs(num-i[1]))
        memo[num] = min(tmpLst)
        return memo[num]

print(dfs(c))