방법만 알면 의외로 깔끔하게 풀리는 DP 문제이다.
https://www.acmicpc.net/problem/1106

목표 고객수를 달성하기 위해 0명부터 순차적으로 고객 수를 달성하기 위해 홍보에 필요한 최소 비용을 저장해 나가는 바텀업 방식이 적합하다 생각했고 이를 위해 C만큼의 크기를 가지는 dp 배열을 만들었다.

• dp의 각 인덱스는 홍보를 통해 달성한 호텔의 고객의 수를 의미하며
• 배열 안의 값은 해당 인덱스 (고객 수)를 달성하기 위한 최소 비용이 저장된다.
• 인덱스 0부터 C까지 순서대로 훑어가는데
  • 매 인덱스마다 모든 홍보를 한 번씩 시도해본다.
  • 현재 고객 수에서 각 홍보를 했을 때 달성될 고객 수를 바라보는데 이 때 더 작은 금액이 저장되도록 dp 배열을 업데이트한다.
  • 홍보를 진행해도 목표고객수(C) 이전이라면 해당 목표 인덱스를 업데이트하고, 홍보를 진행했을 때 목표고객수를 넘어선다면 가장 마지막 인덱스를 업데이트한다.

첫 번째 시도

처음에 생각없이 dp값들을 0으로 초기화 해서 삽질을 좀 했다.

import sys

C, N = map(int, sys.stdin.readline().split())
dp = [0] * (C+1)
ad = list()
for _ in range(N):
    cost, inc = map(int, sys.stdin.readline().split())
    ad.append((cost, inc))
    # 0명인 상태에서 딱 한 번씩 홍보한 결과로 dp를 초기화한다.
    if inc < C:
        dp[inc] = cost
    else:
        dp[-1] = min(cost, dp[-1]) if dp[-1] > 0 else cost
for i in range(C+1):
    for cost, inc in ad:
        if dp[i] > 0:	# dp[i] 가 0인 경우는 홍보가 이루어지지 않은 상태이므로 제외한다.
            if i+inc < C:
            	# 바라보는 dp값이 0이면 그냥 그대로 값을 대입하고, 이미 값이 저장되어 있으면 min값으로 업데이트한다.
                dp[i+inc] = min(dp[i+inc], dp[i] + cost) if dp[i+inc] > 0 else dp[i] + cost
            else:
                dp[-1] = min(dp[-1], dp[i] + cost) if dp[-1] > 0 else dp[i] + cost
print(dp[-1])

내가 보기엔 큰 로직의 문제가 없는데 똑왜틀에 빠졌다. (똑같은데 왜틀려!)
게시판에 있는 모든 반례가 다 통과하는데도 틀렸습니다가 떠서 그 이유를 파악하지 못했다.
음... 일단 내가 파악한 이 코드의 문제점은 궁극적으로 dp값을 min값으로 업데이트 해야하는 문제인데 처음에 0으로 초기화를 했다는게 가장 큰 실수였던것 같다.

별다른 예외케이스를 고려하지않으면 0 때문에 min값이 제대로 업데이트 되지 않고 항상 0으로 고정되는 문제가 생겼기 때문에 0인경우는 어떻게~ 0이 아닌경우는 어떻게~ 와 같은 예외처리를 많이 넣게 되었다.
아마 이 부분 어딘가에서 예외를 제대로 처리하지 못해서 틀린것 같은데 도저히 찾지 못하겠다.

두 번쨰 시도

import sys

C, N = map(int, sys.stdin.readline().split())
dp = [sys.maxsize] * (C+1)
ad = list()
dp[0] = 0
for _ in range(N):
    cost, inc = map(int, sys.stdin.readline().split())
    ad.append((cost, inc))

for i in range(C+1):
    for cost, inc in ad:
        if i+inc < C:
            dp[i+inc] = min(dp[i+inc], dp[i] + cost) 
        else:
            dp[-1] = min(dp[-1], dp[i] + cost)
print(dp[-1])

dp를 0이 아닌 maxsize로 초기화했다.
이러면 min 값으로 업데이트 하는데 아무런 제약이 걸리지 않으므로 고려해야 할 것이 사라진다.
딱 하나 시작점(고객 수가 0인 지점)만 0으로 초기화 해주면 된다.
왜냐하면 (현재시점 가격 + 홍보를 진행했을 때 변동가격)을 가지고 dp 안의 정보와 비교하여 min으로 업데이트 해야 하기 때문에 시작점만 0으로 해야 제대로된 홍보가격 연산이 이루어지기 때문이다. (시작지점도 maxsize면 홍보를 진행했을 때 가격을 구하는 과정에서 오버플로가 난다.)

오늘의 교훈
max를 구하는 문제면 0으로 초기화 하고
min을 구하는 문제면 maxsize로 초기화 하자.