[백준] Swift - 12865번: 평범한 배낭

👆문제풀러 가기👆

문제

 

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

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

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

---

풀이 [메모리: 69888KB,  시간: 208ms]

let nk = readLine()!.split(separator: " ").compactMap { Int($0) }
let (n, k) = (nk[0], nk[1])

var items = [(w: Int, v: Int)]()
// n = 물품 갯수
// k = 최대 무게
// w = 각 물건의 무게
// v = 각 물건의 가치

for _ in 0..<n {
    let wv = readLine()!.split(separator: " ").compactMap { Int($0) }
    items.append((wv[0], wv[1]))
}

// 물건을 추가할 때마다 담기는 무게별 최대 가치
var maxValues = Array(repeating: 0, count: k+1)

for i in 0..<n {
    for j in stride(from: k, to: 0, by: -1) {
        if j >= items[i].w {
            // 기록된 무게별 최대가치와 현재 계산한 물건 가치의 합 비교
            maxValues[j] = max(maxValues[j], items[i].v + maxValues[j-items[i].w])
        }
    }
}

print(maxValues.last!)

DP문제의 가장 대표적인 유형 중 하나이다.

문제에 어떻게 접근해야하는지, 접근하더라도 식을 어떻게 구현해야하는지 등 모든 과정이 어려웠다.

 

처음에는

최대한 가벼운 무게이고, 최대한 가치있는 물건이어야 하지 않을까? 라는 생각으로 정렬했는데,

물건의 갯수가 정해지지 않았기에 더 이상의 코드를 짜기 어려웠다.

 

도저히 감이 오지 않아 다른 블로그를 참고하니 표를 만들어 최대무게(k)까지 각 무게별 최대 무게를 덮어씌우는 것을 보고,

dp풀이법 중 테이블 방식에 대해 조금이나마 이해했고, 이를 점화식으로 표현하는 것이 새로운 관건이었다.

 

이런 표를 기반으로 규칙을 찾아 식을 도출해야했다.

 

처음에는 2차원 배열을 이용해 풀어야하나? 라고 생각했으나,

물건이 추가될 때마다 무게별 최대값이 정리된 배열을 생성할 수 있다면 2차원 배열까지 안 가도 될 것 같았다.

(무게6 -> 0 0 0 0 0 0 13 13)

(무게4 -> 0 0 0 0 8 8 13 13)

 

기존에 기록된 최대가치(maxValues)와 현재 계산될 최대가치(items[i].v + maxValues[j-items[i].w])를 비교해

더 큰 가치를 maxValues에 저장하는 방식을 생각했다.

 

식 도출 방법

무게 4일 때 기존에 기록된 최대가치는(0 0 0 0 8 8 13 13)으로, 

무게 3에서 배낭에 7의 무게를 담았을 때 6 + 8 = 14의 가치를 최대로 들 수 있다.

이 때 6 + 8이라는 가치는 (무게 3 물건의 가치 = 6) + (무게 4 물건의 가치 = 8)를 더한 것이고,

이는 (무게 3 물건의 가치) + (7(기준 무게j) - 무게 3)로 계산할 때 (최대한도 무게)를 담았을 때의 (최대 가치)가 나오게 된다.

[만약 현재 기준무게(j)가 5라면, (무게 j-3의 가치) + (무게 3의 가치)를 기존에 기록된 최대가치인 8과 비교해야 한다. -> 단순히 최대무게(k)와의 비교가 아니라는 의미.]

여기서 앞서 말한 기존에 기록된 최대가치 중 k무게일 때 최대가치인 13과 비교해 더 큰 값을 maxValues에 저장해야 한다.

---

기존의 나는 의사코드로 논리를 글로 작성하며 풀었는데,

배낭문제는 논리의 나열로 풀기엔 어려움이 많은 문제였다.

 

알고리즘 문제가 프론트 개발자에게는 필요없다고들 많이 말하지만,

문제를 다양한 방식으로 접근할 수 있도록 사고를 확장해준다는 점에서 굉장히 좋다고 생각한다.