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

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

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

 

이번 올림피아드대회에서 좋은 성적을 내기 위해서 현수는 선생님이 주신 N개의 문제를 풀고자 한다.

각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어진다.

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야한다.

단, 해당 문제는 주어진 시간이 지나면 풀리는 것으로 간주하며 동일 유형의 문제는 중복해서 풀 수 없다.

 

위의 조건을 모두 충족시키며 최대점수를 출력하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째줄에 문제의 개수 N(1 ≤ N ≤ 100)과 제한 시간 M(10 ≤ M ≤ 1000)이 주어진다.

두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어진다.

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_82.txt', 'rt')

if __name__ == "__main__":
    n, m = map(int, input().split())
    dy = [0]*(m+1)
    for i in range(n):
        ps, pt = map(int, input().split())
        for j in range(m, pt-1, -1):
            dy[j] = max(dy[j], dy[j-pt]+ps)
    print(dy[m])
    
# 출력 : 41

 

input_82.txt(입력)

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

 

 

중요내용

1. 해당 문제에서 중요한 조건 중 하나는 동일유형의 문제를 중복해서 풀 수 없다는 조건이다.
2. 즉, 제한 시간이 남았다고 해서 똑같은 문제를 두 번이상 풀 수 없다.
3. 이러한 중복풀이를 방지하기 위해 1차원 리스트를 활용하는 방법과 2차원 리스트를 활용하는 방법 두 가지가 있다.
4. 하지만 2차원 리스트를 사용하는 경우에는 입력값(N, M)이 커질수록 메모리 사용량이 기하급수적으로 증가하고 시간복잡도, 공간복잡도 문제도 발생한다.
5. 따라서 해당 문제풀이는 1차원 리스트를 활용하는 방식으로 접근한다.
6. 1차원 리스트를 활용하면서 동일 유형 문제의 중복풀이를 방지하는 방법은 해당 리스트를 역방향으로 채워나가는 것이다.
7. 즉, 1차원 리스트의 인덱스번호를 제한시간(M)으로 고려할 때 해당 리스트의 마지막 인덱스번호부터 역으로 벨류 값을 저장하는 방법이다. (ex. for j in range(m, pt-1, -1))
8. 참고로, 1차원 리스트 dy에는 초기값으로 모두 0을 저장한다.
9. dy[j]는 제한시간 j가 주어졌을 때, 문제풀이를 통해 얻을 수 있는 최대점수를 의미한다.
10. 변수 ps는 각 문제를 풀 때 얻는 점수를 의미하고, 변수 pt는 문제 제한시간을 의미한다.