1. 문제

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

1-1) 입력설명

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

1-2) 출력설명

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

1-3) 입력예제

5 20
10 5
25 12
15 8
6 3
7 4

1-4) 출력예제

41

2. 냅색 알고리즘

DP(Dynamic Programming) 방식이며, 작은 것들로부터 결국 원하는 답을 얻는 방식의 알고리즘이다.

3. 코드

import sys
sys.stdin=open("in1.txt", "r")

n, m = map(int, input().split())
dy = [0 for _ in range(m+1)]

for i in range(n):
    p, t = map(int, input().split())
    for j in range(m, t-1, -1):
        dy[j] = max(dy[j], dy[j-t] + p)

print(max(dy))

3-1) 변수 설명

dy: 인덱스 번호는 각 분을 의미하고, 인덱스마다 값은 각 분에서 최대 점수를 의미한다.

4. 설명

기존의 냅색 알고리즘 문제 같은 경우에는 중복을 허용하기 때문에, 앞에서부터 반복문이 실행된다. 하지만 이 문제같은 경우, 한 유형당 한 개만 풀 수 있기 때문에, 다른 방법을 시도해봐야 한다.
먼저 2차원 배열을 사용할 수도 있다. nX(m+1)로 dy를 2차원 리스트로 사용하여, 각 n(행)은 n번째 문제를 포함한 최대점수를 의미한다. 예를 들어 n이 3이라면, 입력예제를 보면, (10, 5), (25, 12), (15, 8) 이렇게 3문제를 포함했을 때 열(분) 값에 최대 점수가 들어가게 되는 것이다. 하지만 2차원 리스트를 사용하면 n, m 값이 커질 수록 공간 복잡도가 커지게 된다. 그렇기 때문에 1차원 리스트로 해결하는 것이 좋다.
위 코드를 보면 1차원 리스트만 사용했고, 기존 냅색 알고리즘과 달리 반복문이 뒤에서부터 실행된다.
1) 2중 반복문이며, 바깥 for문은 n번 반복한다.
2) 이때 input stream으로부터 p(점수), t(시간) 값을 불러오고 안에 있는 for문에 진입한다.
3) j가 도는 for문은 m, 즉 제한시간에서부터 t까지 반복문이 반대로 실행된다.
4) 이때 이루어지는 이벤트는 i번째 반복문이 돌면서 초기화된 dy[j] 값이 이번에 돌고 있는, 새로 비교할 값과 비교하여 더 큰 값으로 dy[j]가 초기화된다.
5)

자료: 인프런 파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 김태원