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

생성일: 2022년 2월 26일 오후 4:50

구현 코드 ⭐

# 최대점수 구하기(냅색 알고리즘) with 2차원 배열
import sys
sys.stdin = open("input.txt", "rt")

if __name__ == "__main__":
    n, m = map(int, input().split())
    dy = [[0 for _ in range(m+1)] for _ in range(n+1)]
    # dy[i][j]는 i번째 문제까지 고려하고 j시간이 주어졌을 때 최대 점수
    for i in range(1, n+1):
        score, time = map(int, input().split())
        for j in range(time, m+1):
            dy[i][j] = max(dy[i-1][j], dy[i-1][j-time]+score)

    print(dy[n][m])

• 이전의 냅색 문제와의 차이점 ⇒ 중복 선택 불가능 ⇒ 이차원 배열을 만들어서 해결해야함 (값을 중복해서 덮어 쓸 수 없기 때문)

• 중복 선택이 없어야 하기 때문에 dy[i][j-time]과 비교하는 것이 아니라 이전에 입력받은 문제를 기준으로 비교해야 한다. ⇒ dy[i-1][j-time]과 비교

• 위와 같이 이차원 배열을 만들어서 문제를 푸는것이 정석이지만, 실전에서 공간복잡도가 매우 증가하는 문제가 있기 때문에 일차원 배열로 간소화하여 푸는 방법도 존재한다.

모범 답안 (1차원 배열 사용) ⭐

# 최대점수 구하기(냅색 알고리즘) with 1차원 배열
import sys
sys.stdin = open("input.txt", "rt")

if __name__ == "__main__":
    n, m = map(int, input().split())
    dy = [0 for _ in range(m+1)]
    # dy[j]는 j시간이 주어졌을 때 최대 점수
    for i in range(0, n):
        score, time = map(int, input().split())
        for j in range(m, time-1, -1):
            dy[j] = max(dy[j], dy[j-time]+score)

    print(dy[m])

• 매우 간단한 아이디어로 1차원 배열을 사용하여 문제를 해결 할 수 있다.
• dy리스트를 채울 때, 0번째(앞)부터 채우는 것이 아니라 m(끝)부터 채우는 것이다.
• 앞부터 채우게 되면 dy[j-time]이 i번째 문제를 이미 푼다는 가정하에 중복적용 하게 된다. 하지만, 뒤부터 채우게 되면 dy[j-time]은 이전문제 까지만 dy에 적용되어있기 때문에 중복 적용의 오류 없이 dy를 채워 나갈 수 있다.