白俊解答1106ホテル

boj 1106:ホテル
質問アドレス:https://www.acmicpc.net/problem/1106
難易度:silver 1
1.問題の説明

ホテルを宣伝します.

少なくとも増加する顧客数C、宣伝できる都市数N.

N都市に宣伝費用と相応の顧客数を与える.

の比率で、費用は3で、お客様が1増加した場合->費用は6,9増加した場合、2,3人増加し、

少なくともC人の顧客を増やそうとしたときの最低コストは?

2.問題を解決する考え.

最初は欲張りだと思っていたが、増え続けた顧客は、料金順に解答しようとしたが、

に失敗した.

DPで解かなければなりません.dpテーブルに記録された最低コストは

で、これは私の顧客を引き付けるために投資されています.
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:]))