백준 1106 호텔

문제

https://www.acmicpc.net/problem/1106

코드

c,n=map(int,input().split())

arr=[]
for _ in range(n):
    a,b=map(int,input().split())
    arr.append((a,b))

dp=[[0]*((c//b+1)*a+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range((c//b+1)*a+1):
        if j<arr[i-1][0]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-arr[i-1][0]]+arr[i-1][1])

for i in range((c//b+1)*a+1):
    if dp[n][i]>=c:
        print(i)
        break

풀이

dp 배낭 문제입니다
dp 테이블의 행을 투자해야되는 돈,열을 도시의 정보로 두고 값을 채울 때
dp[i][j]는 i까지의 도시 정보가 있고 j만큼의 돈이 있을 때 최대로 유치할 수 있는 고객의 수가 됩니다.