| 시간 제한 | 메모리 제한 |
| 1초 | 512MB |
문제
방학을 맞은 귀여운 백남이는 여행을 떠날 준비를 하고 있다.
백남이는 여행에 필요하다고 생각하는 필수품 N개를 가지고 있다. 각 물건은 무게 W와 가치 V를 가진다. 그리고 백남이는 물건을 담을 가방 M개를 가지고 있는데, 각각의 가방은 최대 Ki만큼의 무게를 견딜 수 있다.
MBTI가 J(판단형)인 백남이는 효율성을 중요하게 여기기 때문에, 가장 효율적으로 짐을 싸지 않으면 여행을 출발할 수 없다. 백남이가 정의한 효율성은 (가방에 담긴 물건의 가치의 합) / (가방이 견딜 수 있는 최대 무게)이다.
가방과 물건의 정보가 주어졌을 때, 가장 효율적으로 짐을 싸기 위해 필요한 가방이 무엇인지 알아내자. 가방은 한 개만 선택할 수 있으며, 최적의 가방이 여러 가지라면 그중 가장 작은 번호를 출력한다.
입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 가방의 수 M(1 ≤ M ≤ 100)가 주어진다.
두 번째 줄부터 N 개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
그 후에는 M 개의 줄에 거쳐 가방이 버틸 수 있는 최대 무게 Ki (1 ≤ Ki ≤ 1,000,000)가 주어진다. 가방의 번호는 1부터 M까지이다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 가장 효율적으로 짐을 싸기 위해 필요한 가방의 번호를 출력한다.
풀이
무게 i 이하로 물품을 선택했을 때 최대의 가치를 dp[i]로 관리해보자. 순차적으로 물건을 확인하며 그 물건을 선택하거나 선택하지 않았을 때의 무게 i에서의 최대 가치를 관리할 것이기 때문에 탐색을 시작하기 전에는 모든 i에서 가치가 0이다.
탐색은 이렇게 진행된다. n번째 물건의 무게가 w, 가치가 v이다. i ≥ w일 때, dp[i]의 값은 현재 dp[i]와 dp[i - w] + v 중 큰 값으로 결정된다. 각각의 의미는 이렇다. dp[i]를 그대로 두는 것은 n번째 물건을 선택하지 않는 것이 더 높은 가치를 유지할 수 있다는 의미이고, 갱신하는 것은 n번째 물건을 선택해 i - w의 무게를 이루는 최적의 가치에 현재 물건의 가치를 더해준다는 의미이다.
여기서 n번째 물건은 한 번만 선택할 수 있다. 만약 dp[i]의 갱신이 0에서부터 순차적으로 이루어진다면 dp[i - w]가 dp[i]에 영향을 준 경우, dp[i + w]까지도 영향을 줄 수 있다. 이러면 n번째 물건을 2번 선택하는 것이 된다. 따라서 각 물건의 무게와 가치를 두고 탐색을 진행할 때 dp배열의 끝(K의 최대 값인 1,000,000)부터 0까지 역순으로 탐색하는 것이 좋다.
탐색을 마치고 나면 모든 가방에 대해 그 가방의 최대 무게로 얻을 수 있는 최대 가치의 값을 나눠 가장 높은 값을 저장해주면 문제 해결.
정답 코드
import sys
input = sys.stdin.readline
def solution():
N, M = map(int, input().split())
dp = [0] * 1000001
for _ in range(N):
W, V = map(int, input().split())
for i in range(1000000, W - 1, -1):
if dp[i] < dp[i - W] + V:
dp[i] = dp[i - W] + V
high = 0
result = 0
for i in range(M):
bag = int(input())
k = dp[bag] / bag
if k > high:
result = i
high = k
print(result + 1)
solution()
