백준 12865 문제 풀이 (Python)

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

가방에 넣을 수 있는 무게를 제한해두고 여러 물건 (A,B,C,...)의 가장 효율적인 가치가 나오도록 하려고 한다.

가령, 가치를 $로 나타내자면, 문제에서는
4가지의 물건과 최대 제한 7kg이 주어지고 각각의 물건은

6kg:13$,

4kg:8$,

3kg:6$,

5kg:12$,
가 주어 지는데 6kg이면 13$이지만 주어진 물건 중에서 다른 물건들을 가방에 더 넣을 수 없다.

하지만, 최대 제한인 7kg은 3kg의 물건과 4kg의 물건의 가치를 합쳐 14$가 된다.

비슷한 예시로, 위 물건에서 1kg:4$가 추가되고 제한이 8kg으로 바뀐다면 우리는 4kg + 3kg + 1kg의 경우까지도 계산해볼 수 있다.

 

그렇다면, 제한된 무게까지를 쭉 나열해 나눠 각각 하나의 가방이라 생각하고 각 방에 제한된 무게만큼 물건이 들어올 수 있다.

가방의 무게	0kg까지만	1kg까지만	2kg까지만	3kg까지만	4kg까지만	5kg까지만	6kg까지만	7kg까지만
가치	0	0	0	0	0	0	0	0

처음에는 6kg:13$를 넣어보자.

가방의 무게	0kg까지만	1kg까지만	2kg까지만	3kg까지만	4kg까지만	5kg까지만	6kg까지만	7kg까지만
가치	0	0	0	0	0	0	13	13

무게 제한은 7kg이고 주어진 무게는 6kg이니, 7kg가 제한인 가방에도 들어가고 6kg가 제한인 가방에도 들어간다.

7부터 6까지에 물건의 가치를 넣어야 하니 for문에 range(7, 6-1, -1)를, 변수로 바꿔주면 range(K, w-1, -1)가 된다.

 

7kg까지만의 가방에는 6kg가 들어가서 1kg의 여유 공간이 남지만 표에는 나와있지 않다. 

1kg의 여유공간이 남았는데 우리는 그것을 어떻게 알고 넣을 수 있을까?

임의로 1kg:4$를 추가해 가방에 넣어보겠다.

 

1kg:4$를 추가로 넣는 경우

가방의 무게	0kg까지만	1kg까지만	2kg까지만	3kg까지만	4kg까지만	5kg까지만	6kg까지만	7kg까지만
가치	0	4	4	4	4	4	17	17

6kg까지만의 가방에 7kg가 들어가 버렸다.

7kg까지만의 가방에도 적절하게 6kg와 1kg가 들어가 17$의 가치가 생긴 것을 알 수 있다.

 

적절한 조건을 생각하여 6kg에 7kg가 들어가지 않도록 할 수있다.

제한된 무게(7kg)에 무게(1kg)를 넣게된다. 그렇게 6kg의 여유공간이 남게 되니 전 시행에서의 6kg까지만 가방을 더할 수 있다. 따라서, 판단 시 지금 가방에 그대로 있는 게 좋을 지, 여유공간만큼의 가방의 무게를 더하는 게 좋을 지를 따져서 시행할 수 있다. (여유공간만큼의 가방의 무게를 더하는 방식)은 6kg까지만 가방에 6kg를 넣고 여유공간 0kg까지만 가방을 더하는 것과 7kg까지만 가방에 6kg를 넣고 여유공간 1kg까지만 가방을 더하는 것 처럼,  (맨 처음에 무게제한 만큼만 물건을 넣는 방식)과 동일하다.

가방의 무게	0kg까지만	1kg까지만	2kg까지만	3kg까지만	4kg까지만	5kg까지만	6kg까지만	7kg까지만
가치	0	4	4	4	4	4	13	17

그러므로, 모든 방식을 여유공간만큼의 가방의 무게를 더하는 게 가치가 많이 나갈지, 기존 현상태를 유지할 지를 비교하면 된다. === max(기존 가방의 가치, 여유공간의 무게만큼의 가방의 가치 + 추가되는 가치)

 

임시로 넣은 1kg:4$를 제외하고 계산하면 결과는 다음과 같다.

 

6kg:13$

가방의 무게	0kg까지만	1kg까지만	2kg까지만	3kg까지만	4kg까지만	5kg까지만	6kg까지만	7kg까지만
가치	0	0	0	0	0	0	13	13

4kg:8$

가방의 무게	0kg까지만	1kg까지만	2kg까지만	3kg까지만	4kg까지만	5kg까지만	6kg까지만	7kg까지만
가치	0	0	0	0	8	8	13	13

3kg:6$

가방의 무게	0kg까지만	1kg까지만	2kg까지만	3kg까지만	4kg까지만	5kg까지만	6kg까지만	7kg까지만
가치	0	0	0	6	8	8	13	14

5kg:12$

가방의 무게	0kg까지만	1kg까지만	2kg까지만	3kg까지만	4kg까지만	5kg까지만	6kg까지만	7kg까지만
가치	0	0	0	6	8	12	13	14

 

 

N, K = map(int,input().split())	

lb = [0] * (K+1)	# 제한된 무게만큼의 0kg로 채워진 리스트 생성

for _ in range(N):	# 물건 개수만큼 반복
    w,v = map(int,input().split())	# 무게와 가치 부여
    for i in range(K, w-1, -1):		# 판단하는 무게를 제한된 무게까지만 시행
        lb[i] = max(lb[i],lb[i-w]+v)	# 기존 상태 유지 vs 여유공간만큼의 가방 가치 + 추가되는 가치
print(lb[-1]) 	# 가장 끝쪽의 배열 (7kg)