문제
출처: 백준 - 평범한 배낭 : 12865번
풀이
DP(Dynamic Programming) Knapsack(냅색) 문제다.
냅색 문제는 2개의 짝을 이루는 값이 주어지는데 '무게, 가치', '시간, 가치', '넓이, 가치' 등이다. 이렇게 짝을 이룬 값이 주어질 때 이 값이 중복으로 사용할 수 있느냐 없느냐로 풀이가 조금 달라진다.
값이 여러개(무한)으로 주어질 때에는 중복을 허락하기에 가방 무게만큼의 1차원 배열에 순서대로 물건을 업데이트하며 중복으로 계산이 가능하다.(참고: 값이 무한일 때)
하지만 문제에서 주어진대로 가방에 넣을 수 있는 물품은 하나만 존재하기에 값이 무한으로 주어질 때의 냅색 알고리즘 방식으로 값을 업데이트 할 수 없다. 왜냐하면 냅색 방식은 '현재의 값 VS 이전의 값에 현재 물건의 가치를 더한 값' 중에서 더 높은 값을 업데이트 하기에 중복이 되기 때문이다. 그래서 문제에서와 같이 하나의 값이 주어질 때에는 '물건의 개수(행) * 가방의 무게(열)'의 2차원 배열이 필요해진다.
그런데 문제의 조건을 보면 물품의 개수 100 * 무게 100,000만큼의 2차원 배열을 생성하게 되면 1억 만큼의 공간 복잡도가 생기기 때문에 오답으로 판정된다. 파이썬은 1초에 1000만회 미만의 시간 복잡도를 써야 하듯이 공간 복잡도 또한 1,000만을 넘기게 되면 오답을 반환한다. C 언어로 풀어도 오답처리가 되도록 1억으로 설정된 것을 볼 수 있다.
2차원 배열처럼 1차원으로 배열을 업데이트 하는 방법은 마지막 인덱스부터 업데이트하는 것이다. 이런 방식으로 업데이트를 하게 되면 중복으로 값이 업데이트 되지 않는다.
코드
2차원 방식 코드
n, k = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(n)]
sack = [[0] * (k + 1) for _ in range(n + 1)] # '물건의 개수(행) * 가방의 무게(열)' 의 2차원 배열 생성
for i in range(n):
v, w = items[i] # 물건을 첫 번재 인덱스 부터
for j in range(w, k + 1): # 해당 물건의 무게 부터 가방 무게까지
# 행 1(i + 1)이 물건 첫 번째 물건에 대한 무게별 가치 업데이트 구간, i행은 참조
sack[i + 1][j] = max(sack[i][j], sack[i][j - w] + v)
print(sack[n][k])코드
n, k = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(n)]
sack = [0] * (k + 1) # 1차원 배열 생성
for w, v in items:
for j in range(k, w-1, -1): # 가방의 무게부터(뒤에서부터) 앞으로 무게에 대한 가치 업데이트를 하면 중복이 되지 않고 업데이트 된다.
sack[j] = max(sack[j], sack[j - w] + v)
print(sack[k])