풀이 과정
배낭 문제인데 중복해서 물건이 여러개가 있을 수 있는 경우이다.
맨처음에는 재귀를 사용해서 구현하는데 재귀함수에 매개변수를 3개(무게, 만족도, 개수)를 넣어주면 되지 않을까..? 라고 생각을 했다.
그러나 이렇게 구현하는 경우 dp 배열을 3차원으로 해야하고 최악의 경우 그 크기가 10000 * 10000으로 1억이나 되서 메모리 초과가 발생할 것 같아서 다른 방법을 생각해야했다.
메모리 초과를 피하기 위해 재귀가 아닌 반복문으로 구현하고 dp 배열도 일차원으로 구현하려고 생각을 했다.
그랬더니 여러 물건이 들어오는 경우 그 개수만큼 물건 배열에 추가로 저장을 해주면 되는거 아닌가...? 라는 생각이 들었다.
예를 들어 개수가 12인 물건이 들어오면 물건 배열에 12번 물건을 넣어주는 것이다.
이 생각은 실제로 정말 좋은 아이디어였지만 최악의 경우 이번엔 물건 정보를 담아주는 배열의 크기가 1억이나 돼서 다른 아이디어를 떠올려야 했다.
결국 구글 검색을 한 결과,,, 이전에 했던 방법의 업그레이드 버전이 있다는걸 알게되었다.
(1, 2, 4) 라는 숫자의 조합으로는 1~7까지 나타낼수가 있는데 이에따라 (1, 2, 4, 5)의 숫자 조합으로는 1~12까지 숫자를 나타낼수 있다.
예를들어 개수가 12이고, 물건의 무게와 만족도가 각각 V, C인 물건이 입력으로 들어왔다면 이 물건을 (V,C) (2V,2C) (4V,4C) (5V,5C)인 물건들로 분해해서 배열에 저장해주면 된다.
이때, 물건의 개수를 10개 선택했다면 위 물건들에서 (V,C) (4V,4C) (5V,5C)인 물건을 선택했다고 생각하면 되는것이다.
이렇게 해주면 하나씩 저장 해주는것보다 저장해주는 물건의 개수가 현저히 적어지게 된다.
배낭문제 공부하고 비슷한 유형 문제 하나 더 풀어보려다가 엄청 고생했다...
최종 코드
N, M = map(int, input().split(' '))
dp = [0 for _ in range(M + 1)]
objects = []
for _ in range(N):
W, C, K = map(int, input().split(' '))
i = 1
while K > 0:
m = min(i, K)
objects.append((W * m, C * m))
K -= i
i *= 2
for W, C in objects:
for i in range(M, W - 1, -1):
dp[i] = max(dp[i], dp[i - W] + C)
print(dp[M])
결과
Link
