[Softeer] 금고털이 (level 2, 냅색 알고리즘, DP)

사용 언어: Python3

문제

풀이

나의 풀이

import sys

W, N = map(int, input().split())
lst = []
for _ in range(N):
    w, p = map(int, input().split())
    lst.append((w, p))

lst.sort(key=lambda x:x[1], reverse=True)

price = 0
i = 0
while W != 0:
    if W >= lst[i][0]:
        W -= lst[i][0]
        price += lst[i][1] * lst[i][0]
    else:
        price += lst[i][1] * W
        W = 0
    i += 1

print(price)

• 테스트 케이스: 성공
• 제출 결과: 성공

나의 풀이 - DP (230729 추가)

W, N = map(int, input().split())
lst = [tuple(map(int, input().split())) for _ in range(N)]

dp = [0] * (W+1)

for weight, value in lst:
    for i in range(W, 0, -1):
        tmp = i if i < weight else weight # tmp: 필요한 보석 무게 (보석은 필요한 만큼 자를 수 있음)
        dp[i] = max(dp[i], dp[i-tmp]+value*tmp)

print(dp[W])

• 테스트 케이스: 성공
• 제출 결과: 시간 초과 🥵

다른 풀이 - 그리디 (230729 추가)

W, N = map(int, input().split())
lst = [tuple(map(int, input().split())) for _ in range(N)]

lst.sort(key=lambda x:x[1], reverse=True)

ans = 0
for weight, value in lst:
    if W >= weight: # 전체 사용
        W -= weight
        ans += weight * value
    else: # 잘라서 넣어주어야 함
        ans += W * value
        break

print(ans)

• 테스트 케이스: 성공
• 제출 결과: 성공
• 무게당 가격이 높은 순 정렬해서 가방에 넣어준다.

---

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

맨 위로 이동하기