[백준] 16493. 최대페이지 수

N=7, M=7일때 

dp[i]와 dp[i-day]+page 중 더 큰 값을 dp[i]에 넣는다!

(day,page)	0	1	2	3	4	5	6	7
(2,200)	0	0	200	200	200	200	200	200
(4,40)	0	0	200	200	200	200	240	240
(5,20)	0	0	200	200	200	200	240	240
(1,20)	0	20	200	220	220	220	240	260
(2,15)	0	20	200	220	220	235	240	260
(3,10)	0	20	200	220	220	235	240	260
(1,10)	0	20	200	220	230	235	245	260

n,m=map(int,input().split())
bag=[]
for i in range(m):
    day,page=map(int,input().split())
    bag.append((day,page))
bag.sort(key=lambda x:-x[1])

dp=[0]*(n+1)
for day,page in bag:
    for i in range(n,day-1,-1):
        dp[i]=max(dp[i],dp[i-day]+page)
        #dp[i], dp[i-2]+200
        #dp[i], dp[i-4]+40
        #dp[i], dp[i-5]+20
        #dp[i], dp[i-1]+20
        #dp[i], dp[i-2]+15
        #dp[i], dp[i-3]+10
        #dp[i], dp[i-1]+10
    print(dp)


print(dp)