[골드5]백준 12865번(평범한 배낭) - 코테공부 36일차(2025.02.26)

문제유형

다이나믹 프로그래밍(동적 계획법)

풀이 방법 도출 과정

1. 물건 N개의 물건이 있다. 각 물건은 무개W와 가치 V를 가지는데 최대 K만큼의 무개만큼 넣는다고 가정했을 때, 가치V가 가장 높을 때의 값을 구하는 문제이다.

2. 첫 줄에 입력은 N, K 나머지는 W, V이다.

 

3. 가장 먼저 일단 가장 W가 채워질 가능성을 찾고 그 뒤로 그 가능성 중에 가장 나은 것을 고르는 방법이 있다. 이 방법은 최악의 경우 100C50이 나오는데 이는 1억을 넘는 것이기에 사용하지 않겠다. 

4. 두번째로 그리디 알고리즘을 사용하는 방법이 있는데 이를 위해 가치 대비 무개 비율이 높은 순서대로 정렬한 다음 가능한 한 많은 물건을 선택한다고 해서 정확한 최적해를 보장하기에는 적절하지 않다.

 

5. 그러므로 동적 계획법을 생각할 수 있는데 메모제이션을 통해서 1차원 배열로 나누어서 계산하게 하면 시간복잡도 문제는 해결이 된다.

시간 복잡도

시간 복잡도는  O(N*K)이다. 

코드 및 간단설명

동적 계획법을 사용하였다.

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

dp = [0] * (K + 1)

for w, v in items:
    for j in range(K, w - 1, -1):  # 뒤에서부터 업데이트
        dp[j] = max(dp[j], dp[j - w] + v)

print(dp[K])

다른 풀이

1)  동적계획법에서 정렬을 사용하여 시간복잡도를 줄였다. 

이 방법은 sys를 사용하여 시간복잡도를 줄이고 결정적으로 정렬을 사용하여 시간복잡도를 다른 것보다 더 줄였다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

arr = [list(map(int, input().split())) for _ in range(n)]
arr.sort(key=lambda x: x[0])

dp = [0] * (k+1)

for i in range(1,n+1): #물건
    w, v = arr[i - 1]
    for j in range(k,w-1, -1): #무게
        dp[j] = max(dp[j], dp[j-w]+v)

print(dp[k])