boj 1106 : 호텔

문제 주소: https://www.acmicpc.net/problem/1106

난이도: silver 1

1.문제설명

• 호텔을 홍보하려한다.
• 최소한 늘려야할 고객의 수가 C, 홍보할수 있는 도시의 개수가 N으로 주어진다.
• N개의 도시에 대해서 홍보비용과 그에 맞는 고객수가 주어진다.
• 일종의 비율로 비용이3이고 고객이 1 늘어난다고하면 -> 비용을 6, 9로하면 2,3명 늘어난다
• 이때 최소 C명의 고객을 늘리려할때 최소 비용은?

2.문제해결 아이디어.

• 처음엔 greedy로 생각했다, 리스트를 늘어나는 고객, 비용 순으로 정렬해서 풀이 시도했지만 실패
• DP로 풀어야 했음. dp테이블에 기록하는 것은 고객을 i명 유치하기 위해 투자해야하는 최소 비용

3.문제접근법

#낮은 가격순으로 순회하며 업데이트 시켜줄것이기 때문
advertise.sort(key=lambda x : x[0]) 
# C+100을 해준이유는 최소값이 C를 초과한 경우에 생기는 케이스가 있을 수 있음
dp = [INF]*(C+100) #100은 문제의 조건에 있음 홍보로 얻을수 있는 고객의 최대값
dp[0] = 0 #테이블 초기화

#테이블 업데이트
for cost, new_pep in advertise:
    for i in range(new_pep, C+100):
        dp[i] = min(dp[i-new_pep] + cost, dp[i])

4.특별히 참고할 사항

• 그리디가 최적해를 구하지못하는 경우의 좋은 예

5.코드구현

import sys
input = sys.stdin.readline
INF = 1e9
C, N = map(int, input().split()) #c ->늘려야할 최소고객수, N - > 도시개수
advertise = []

for _ in range(N):
    temp = list(map(int, input().split())) #비용, 고객수
    advertise.append(temp)

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

dp = [INF]*(C+100)
dp[0] = 0

for cost, new_pep in advertise:
    for i in range(new_pep, C+100):
        dp[i] = min(dp[i-new_pep] + cost, dp[i])

print(min(dp[C:]))