최대 페이지 수 (백준 16493)

n,m = map(int, input().split())
read = [[0,0]]
for i in range(m):
    read.append(list(map(int, input().split())))

dp =[[0]*(n+1)for _ in range(m+1)]
for i in range(1, m+1):
    for j in range(1,n+1):
        d,p = read[i][0],read[i][1] 
        if j < d : 
            dp[i][j] = dp[i-1][j] 
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-d]+p)
print(dp[m][n])

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

16493번: 최대 페이지 수

 

  첫 번째 책부터 시작해서 계속 최대의 경우를 택해야 한다. 그래서 2차원의 dp 배열이 필요하다.