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

12865번: 평범한 배낭

---

나의 풀이

let NK = readLine()!.split(separator: " ").map { Int($0)! }
let N = NK[0]
let K = NK[1]
var goods = Array(repeating: [Int](), count: N+1) // [weight, value]
for i in 1...N {
    goods[i] += readLine()!.split(separator: " ").map { Int($0)! }
}

var dp = Array(repeating: Array(repeating: 0, count: K+1), count: N+1)
for i in 1...N {
    let weight = goods[i][0]
    let cost = goods[i][1]
    for j in 1...K {
        dp[i][j] = dp[i-1][j]
        if j >= weight {
            dp[i][j] = max(dp[i][j], dp[i-1][j-weight] + cost)
        }
    }
}
print(dp[N][K])

풀이 키워드

DP
goods라는 2차원배열에 물건을 넣어가며 수납 가능 무게마다 최대 수납 value를 기억하여
제일 큰 value값을 반환한다.
이게 생각보다 이해하기 어려웠으며, 값을 기억해 놨다가 필요할 때 써가며 또 저장한다는 매커니즘을 완전히 이해할 필요가 있다.

 

시간복잡도를 개선한 풀이

let NK = readLine()!.split(separator: " ").map { Int($0)! }
let N = NK[0] // 물품의 수
let K = NK[1] // 버틸 수 있는 무게

var dp = Array(repeating: 0, count: K+1)
for _ in 0..<N {
    let WV = readLine()!.split(separator: " ").map { Int($0)! }
    let W = WV[0] // 물품의 무게
    let V = WV[1] // 물품의 가치
    
    for i in stride(from: K - W, through: 0, by: -1) {
        if (i == 0 || dp[i] > 0) && dp[i] + V > dp[i+W] {
            dp[i+W] = dp[i] + V
        }
    }
}
print(dp.max()!)

풀이 키워드

DP
1차원 배열로 DP를 활용해 푼 풀이다.
위의 풀이와 전반적인 풀이 매커니즘은 같다.
물건을 넣을 때 마다 무게에 가능한 최대치를 넣고
다음 물건을 넣을 때 남는 무게와 현재 무게의 value가 현재 무게의 value보다 높다면
높은 value를 기억하며 푸는 방식이다.
stride()로 반복문을 제한하기 때문에 더 낮은 시간복잡도가 된 거 같다.

---