배낭문제가 이해가 잘 안돼서 정리해 보았다.
이 문제에서 중요한 부분은 hotel[명] = 원 리스트를 만들고 min(hotel[i], hotel[i-cus]+cost) 이 식을 찾을 수 있느냐이다.
다른 배낭문제에서도 두가지의 값이 나오는데(무게, 가치) 이를 dp 테이블에 넣고, 값을 포함했을 때와 아닐 때를 비교해주는 것이 문제의 핵심이다.
CODE
import sys
input = sys.stdin.readline
C, N = map(int, input().split())
# 비용(cost)과 고객 수(cus)를 입력받기 위한 data 리스트
data = [list(map(int, input().split())) for i in range(N)] # [[비용,고객]]
data = sorted(data, key = lambda x: x[0]) C는 목표 고객 수 이지만, 적어도 C 명 늘이기 위한 금액을 구하는 문제로 더 클 수도 있다.
비용이 적은 수 부터 넣어주어야 min값을 찾을 때, 적은 값과 나중에 들어온 큰 값을 비교할 수 있다.
INF = 1e9 # 비용이 매우 클때를 가정하고 무한히 큰 수를 지정
hotel = [INF for i in range(C+100)] # 비용을 담을 리스트 hotel[명] = 원
hotel[0]=0 # 고객 0명일때 비용 0범위가 C+100인 이유는 비용으로 얻을 수 있는 고객의 수(cus)가 100보다 작거나 같은 값이기 때문이다.
예를 들어 C = 1이고 1원으로 100명의 고객을 얻을 수 있다면 hotel[100]=1이다. hotel은 [0,1000,1000,...,1] 그러므로 범위는 C+100이 된다.
for cost, cus in data: # 비용과 고객 수를 뽑아서 for문을 돈다.
for i in range(cus, C+100): # cus로 시작하는 것은 cus명을 채우기 위해 드는 비용을 찾기 위해서이다.
hotel[i] = min(hotel[i], hotel[i-cus]+cost) # min(i명 채웠던 비용, cus명 채우기 전 비용 hotel[i-cus]+ 현재 비용(cost))
print(min(hotel[C:])) # C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값여기서 중요한 것은 hotel[C]로 찾으면 안된다는 것이다. '적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값' 이라고 했으므로 적어도 C명 이상을 채울 수 없는 값을 찾되, 더 많은 사람을 찾을 수 있는 hotel[C:] 범위에서 최솟값을 구해야한다.
다른 배낭문제와 달리 고려해주어야 하는 부분이다.
입력 예시
10 3
3 1
2 2
1 3
출력 예시
[[1, 3], [2, 2], [3, 1]]
cost와 cus를 cost가 작은 수로 정렬한 모습이다.
[0, 1000000000.0, 1000000000.0, 1, 1000000000.0, 1000000000.0, 2, 1000000000.0, 1000000000.0, 3, 1000000000.0, 1000000000.0]
첫번째 for문에서 1원으로 3명을 채우는 모습이다. (편의를 위해 일단 hotel[:11]까지 잘랐다.)
[0, 1000000000.0, 2, 1, 4, 3, 2, 5, 4, 3, 6, 5]
두번째 for 문에서 2원으로 2명을 채우는 모습이다. cost = 2, cus = 2
hotel[5] = 3 3원으로 5명을 채우는 경우, cus 2명을 채우기 전(hotel[5-2] = hotel[3]= 1) 1원에 현재 cost 2원을 더해서 3원을 만드는 것이 최적이다.
[0, 3, 2, 1, 4, 3, 2, 5, 4, 3, 6, 5]
세번째 for문에서 3원으로 1명을 채우는 모습이다. cost = 3, cus = 1
[0, 3, 2, 1, 4, 3, 2, 5, 4, 3, 6, 5, 4, 7, 6, 5, 8, 7, 6, 9, 8, 7, 10, 9, 8, 11, 10, 9, 12, 11, 10, 13, 12, 11, 14, 13, 12, 15, 14, 13, 16, 15, 14, 17, 16, 15, 18, 17, 16, 19, 18, 17, 20, 19, 18, 21, 20, 19, 22, 21, 20, 23, 22, 21, 24, 23, 22, 25, 24, 23, 26, 25, 24, 27, 26, 25, 28, 27, 26, 29, 28, 27, 30, 29, 28, 31, 30, 29, 32, 31, 30, 33, 32, 31, 34,
33, 32, 35, 34, 33, 36, 35, 34, 37, 36, 35, 38, 37, 36, 39]
d[10] = 6 인데, d[12] = 4이다. 즉 12명을 채우는 것이 더 최솟 값이므로 이를 답으로 출력해야 한다.