[파이썬 알고리즘 문제풀이] - Section8 / Dynamic programming(동적계획법) - 10

최대점수 구하기(냅색 알고리즘)

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

▣ 입력설명
첫 번째 줄에 문제의 개수N(1<=N<=100)과 제한 시간 M(10<=M<=1000)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

▣ 출력설명
첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

▣ 입력예제 1
5 20
10 5
25 12
15 8
6 3
7 4

▣ 출력예제 1
41

import sys
# sys.stdin = open("input.text", "rt")
# input = sys.stdin.readline

#제한시간 m안에 n개의 문제 중 최대점수 얻기

n, m = map(int, input().split())
#제한시간까지의 최대점수... dp 냅색 알고리즘? 
#dp 테이블에는 제한시간 내 최대점수가 들어가야겠다.
data = []
for _ in range(n):
    a,b = map(int, input().split()) #점수, 시간
    data.append((a,b))

dp = [0] * (m+1)
for i in range(len(data)):
    score, time = data[i][0], data[i][1] 
    for j in range(m, time-1, -1): # 제한시간 m부터 해당 문제의 시간인 time까지
        dp[j] = max(dp[j], dp[j-time] + score) #현재 문제를 푼다고 가정했을 때의 최대점수 dp[j-time] + score
    
print(dp[m])

🏈 코멘트

지금까지 풀어본 냅색 알고리즘 문제들, 가방문제, 동전교환 문제를 보면 가방문제는 한 종류의 보석을 무한개씩 써도 상관없고, 동전교환 문제 역시 한 동전을 무한개씩 써도 상관없었다.

이 문제는 한 유형에 하나만 풀 수 있다는 조건이 걸려있다. 즉 중복해서 풀 수 없다는 것이 이 문제의 핵심이었다.

중복이 안되게 하기 위해서 앞에서부터가 아닌 뒤에서부터 적용하면 된다.