백준 16493 최대 페이지 수

문제 URL : https://www.acmicpc.net/problem/16493

16493번: 최대 페이지 수

문제 접근법 : 

할수 요소일 수에서 가장 많은 페이지를 보는게 이득입니다.

 

m 이20이라 재귀로 전수조사해도 2^20이라 100만 으로 충분히가능하고

재귀 + 메모이제이션 은 더빠르게 가능하고

 

어차피 배낭문제로 반복문으로 해결하는게 가장 빠르게 가능합니다.

 

소스코드 : 

import sys
input = sys.stdin.readline
n,m = map(int,input().rstrip().split())
l = [list(map(int,input().rstrip().rsplit())) for i in range(m)]
dp = [0]*(n+1)
for i in range(m):
    for j in range(n,-1,-1):
        if j-l[i][0]>=0:
            dp[j]=max(dp[j],dp[j-l[i][0]]+l[i][1])
print(dp[n])

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.