백준 23061번 백남이의 여행 준비

문제

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

방학을 맞은 귀여운 백남이는 여행을 떠날 준비를 하고 있다.

백남이는 여행에 필요하다고 생각하는 필수품 N개를 가지고 있다. 각 물건은 무게 W와 가치 V를 가진다. 그리고 백남이는 물건을 담을 가방 M개를 가지고 있는데, 각각의 가방은 최대 K_i만큼의 무게를 견딜 수 있다.

MBTI가 J(판단형)인 백남이는 효율성을 중요하게 여기기 때문에, 가장 효율적으로 짐을 싸지 않으면 여행을 출발할 수 없다. 백남이가 정의한 효율성은 (가방에 담긴 물건의 가치의 합) / (가방이 견딜 수 있는 최대 무게)이다.

가방과 물건의 정보가 주어졌을 때, 가장 효율적으로 짐을 싸기 위해 필요한 가방이 무엇인지 알아내자. 가방은 한 개만 선택할 수 있으며, 최적의 가방이 여러 가지라면 그중 가장 작은 번호를 출력한다.

 

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 가방의 수 M(1 ≤ M ≤ 100)$가 주어진다.

두 번째 줄부터 N 개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

그 후에는 M개의 줄에 거쳐 가방이 버틸 수 있는 최대 무게 K_i (1 ≤ K_i ≤ 1,000,000)$가 주어진다. 가방의 번호는 1부터 M까지이다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 가장 효율적으로 짐을 싸기 위해 필요한 가방의 번호를 출력한다.

2. 코드

import sys

input = sys.stdin.readline

# 입력
n, m = map(int, input().split())

# 물건의 가치 와 무게을 담을 배열
thing = []

# 가방의 무게를 담을 배열
bag = []

num = 0
answer = 0

# 입력
for _ in range(n):
    thing.append((list(map(int, input().split()))))

# 입력
for _ in range(m):
    bag.append(int(input()))

# 가방 무게의 최댓 값으로 dp 이중 배열을 설정 해야 시간 초과를 예방 할수 있다.
dp = [[0] * (max(bag) + 1) for _ in range(n + 1)]


# 일반 적인 냅색 코드이다.
for i in range(1, n + 1):
    for j in range(1, max(bag) + 1):
        w = thing[i - 1][0]
        v = thing[i - 1][1]

        if w > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)

# 효율성 계산
for i in bag:
    p = dp[n][i] / i
    if answer < p:
        answer = p
        num = bag.index(i)
# 인덱스 출력
print(num + 1)

3.문제를 보고 든 생각

1. 일반 적인 냅색 문제 라고 생각 했다. 그래서 일반적으로 가방 하나하나 다 냅색 알고리즘을 돌렸다가 시간 초과 와 메모리 초과를 맞았다.

2. 다른 해결 방법은 가방의 최대 무게로 냅색 알고리즘을 돌리면 해결 될것 이라고 문득 생각이 들었다.

3. 이를 통해서 문제 를 해결 할수 있었다.

 

4.고쳐야 할점

더 좋은 방식이 있다면 댓글로 알려주세요