[김태원 알고리즘] 최대점수 구하기 (냅색 알고리즘, DP)

사용 언어: Python3

문제

이 문제는 한 유형당 한 개만 풀 수 있다는 것이 핵심이다!

풀이

2차원 dp 리스트 이용

from copy import deepcopy

N, limit = map(int, input().split())
lst = list(tuple(map(int, input().split())) for _ in range(N))
dp = [[0] * (limit + 1) for _ in range(N + 1)]

for i in range(1, N+1):
    dp[i] = deepcopy(dp[i-1])
    score, time = lst[i-1] # lst의 0번 인덱스가 1번 문제
    for j in range(time, limit+1):
        # i번째 문제를 푼 것(dp[i-1][j-time] + score)보다 풀지 않은게(dp[i][j]) 더 크다면 문제를 풀지 않는다
        dp[i][j] = max(dp[i-1][j-time] + score, dp[i][j]) 
print(dp[N][limit])

• 정답!
  • 그런데 메모리를 너무 많이 잡아먹는다.

1차원 dp 리스트 이용 🌟

N, limit = map(int, input().split())
lst = list(tuple(map(int, input().split())) for _ in range(N))

# dp : 제한 시간이 index일 때 얻을 수 있는 최대 "점수"
dp = [0] * (limit + 1)

for score, time in lst:
    print(dp)
    for j in range(limit, time-1, -1): # ✅ 2차원 리스트를 사용하지 않으려면 거꾸로 돌기
        dp[j] = max(dp[j-time] + score, dp[j]) # ✅

print(dp[limit])

• 정답!
• for문을 뒤에서부터 돌면 dp[j-time] 부분에서 아직 갱신되지 않은 값을 읽어오기 때문에 2차원 리스트를 사용하지 않고도 같은 효과를 낼 수 있다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기