[Swift][DP] 백준 12865 (평범한 배낭)

요구능력 : DP문제풀이능력

 

코드설명 : 

 

문제에 대한 설명은 다른 블로그를 참고했는데 여기 보다 잘 설명할 자신이없어서 소개드립니다.

 

내가 이해한걸 그대로 적어보면 우선 이 dp문제는 2차원dp이다.

처음에 1차원으로 풀어보려다가 뭔가 1차원으로 푸는게 말이안되는 느낌이 들어서 2차원으로 풀기시작하다가 풀이를봤다.

그런데 역시나 2차원으로 풀리는 dp문제는 표를 그려서 푸는게 가장 이상적인것같다.

 

이곳에 표를 그려서 푸신 분이 계신다.

 

내가 가장헷갈렸던 부분은 이 중 for문안에 첫번째 조건인 if j >= items[i - 1][0] 부분인데

왜 저렇게 작은 수부터 시작하지 싶었지만 이 문제는 dp이고 j는 배낭무게이기 때문에 배낭무게에 따라 최대값을 구해주는게 맞는거였다.

 

그리고 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i - 1][0]] + items[i - 1][1] ) 이 부분도 헷갈렸다.

j - items[i - 1][0] 특히 이 부분인데 표를 그려서 하면 이해하기 쉽다.

예를들어 3번째 물건에 배낭무게가 3인 배낭을 구한다고하면 같은 무게의 그 전의 dp[2][3] 과 dp[2][3 - 현재 물건의 무게] + 현재 물건의 가치를 비교해줘야 한다. 그래야 무게가 맞는다.

dp[3][3] = max(dp[2][3], dp[2][3 - 현재 물건의 무게] + 현재 물건의 가치

현재 물건의 무게가 2라면 이전 dp[2][1]에 현재 물건의 가치를 더해줘야 무게가 [3]이 된다.

 

후기 : 전혀 평범하지 않은 배낭인거같다.

let nk = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nk[0]
let k = nk[1]
var dp = Array(repeating: Array(repeating: 0, count: 100001), count: 100001)
var items = [[Int]]()

for _ in 0..<n{
    let wv = readLine()!.split(separator: " ").map{Int(String($0))!}
    items.append(wv)
}

for i in 1...n{
    for j in 1...k{
        if j >= items[i - 1][0] {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i - 1][0]] + items[i - 1][1] )
        }else{
            dp[i][j] = dp[i - 1][j]
        }
    }
}
print(dp[n][k])