[백준] (Swift) 12865번 - 평범한 배낭 (dp, 2차원 dp, Knapsack 알고리즘)

 

🟠 문제 링크

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

🟠 풀이 방법

어렵다... 역시 아직 골드는 무리인가 ㅠㅠ  그래도 '2차원 dp를 이용해야되는구나!'를 눈치채긴 했다. 단,, 어떻게 이용하느냐를 몰랐지 ㅠㅠ 인터넷을 찾아보니까, 해당 문제는 굉장한 well-known 문제라고 한다. (학교 알고리즘 수업에서도 자주 등장하는 아주 단골이라는?! (나 비전공자 ㅠㅠ ))

그래서 일단 dp를 어떻게 만들어야하는지 천재들이 풀어놓은 풀이를 보고 조금 감을 잡고, 그림을 그려가면서 풀어보았다. (이게 이해는 되는데 말로 설명이 어렵더라구요..?)

일단... 그림을 그리면 이렇게 된다. 

차례대로 1행부터 훑으면서 진행된다.

• DP 안에 값으로는 문제에서 주어진 V 값이 들어갈 것
• dp[i][j]에서 i는 배낭에 넣을 물건 번호
• dp[i][j]에서 j는 현재 배낭의 무게 → 즉, j의 최대 값은 주어진 K가 된다.

우선 이 문제의 핵심은, 물건을 계속해서 더해보는데, 무게 K를 넘으면 안된다는 조건이 있다. 이 조건을 지키기 위해서 우리는 j 값에 주목해야한다.

• [1][6] 을 보자. 13이 들어가있다.
  • 1번물건의 무게가 6이기 때문에 j=6인 곳에 1번물건을 넣을 수 있었던 것이다.
  • 사실 이전 단계부터 살펴보면, 지금 넣을려는 1번 물건의 무게가 6이기 때문에, "j = 6(현재가방의무게) - 6(1번물건의무게) = 0" 그니까 가방무게가 0인 경우에서 1번물건을 넣을 수 있다. 그래서 해당 값은 [1][0] + v[1] = 0 + 13 라고 볼 수 있다. 
• [1][7]을 보자. 그대로 13이 들어가있다.
  • 마찬가지로, 1번물건은 무게가 6이다. [1][7]에 만약 1번물건을 넣으려고 한다면, [1][1] 일때 넣을 수 있을 것이다. 그럼 결국 [1][1] + v[1] = 0 + 13 이 되었을 것이다. 
• [2][5]를 보자. 8이 들어가있다.
  • 2번 물건의 무게는 4이다. 현재 가방무게는 5 이기 때문에 1일때 2번물건을 넣을 수 있었을 것이다. 그럼 [2][1] + v[2] 를 더했기 때문에 8이 나왔을 것이다.
• [2][6]을 보자. 13이 들어가있다
  • 우리가 앞에서 진행해오다가 간과한게 있는데, 우리는 순서대로 더하는것 뿐만 아니라, 이전의 모든 경우의 수를 생각해서 최대값을 찾아야한다. 
  • 일단, [2][6]에 넣을 값은 [2][2] + v[2] 값인 8이 될 것이다. 근데 왜 13이 되었는가?
  • 이유는, 우리는 [2][6]에 무게 6을 맞춰 넣을 수 있다. 그럼, [1][6]과도 비교해주어야하지 않겠는가?? 우리는 어쨌든 최대값을 찾고 있어서, 가방 무게가 6이 만들어질 때, 1번물건을 넣었을때 그 값이 최대인지, 2번물건을 넣었을때 그값이 최대인지도 고려해주어야한다. 
  • 그래서 [1][6] vs. [2][2]+v[2] 두개의 값을 비교해서 더 큰 값인 13을 넣어준 것이다.

이정도 살펴보았으면, 대충 점화식이 보인다. 

dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]]+v[i])

 

 

 

⛔️ 여기서 잠깐,,, dp[i][j-weight[i]]+v[i] 이거 인데, 왜 통과가 안돼? 왜 dp[i-1]... 이라고 해야하지???? 진짜 이해안돼.. (이것도 인터넷보고 겨우 해결한거임)

 

아래 적어놓을게요 아시는분 댓글 부탁드리겠습니다.. 왜 dp[i-1]인가????? 아. . 스터디원들한테 물어봐야지... 다른 풀이들도 다 보면 dp[i]라고 써놓고 코드는 dp[i-1] 이라고 해놧네 ;; ㅠㅠ 

 

🟠 전체코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/12865_%ED%8F%89%EB%B2%94%ED%95%9C%20%EB%B0%B0%EB%82%AD/main.swift

GitHub - deslog/Algorithm

let nk = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nk[0]
let k = nk[1]
var weigth = [Int]()
var value = [Int]()
weigth.append(0)    // index 1로 맞춰줄라고 0 넣어줌
value.append(0)
for _ in 0..<n {
    let temp = readLine()!.split(separator: " ").map { Int(String($0))! }
    weigth.append(temp[0])
    value.append(temp[1])
}
var dp = Array(repeating: Array(repeating: 0, count: k+1), count: n+1)

for i in 1..<n+1 {
    for j in 1..<k+1 {
        if i == 1 {   // 1번 물건일 때는 j가 1번무게보다 크면 그냥 바로 넣어줌
            if j >= weigth[i] {
                dp[i][j] = value[i]
            }
        } else {     // 2번 물건부터 비교하면서 시작
            if weigth[i] > j {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weigth[i]]+value[i])
                // ⚠️ dp[i][j] = max(dp[i-1][j], dp[i][j-weigth[i]]+value[i]) 이거 왜 아니야?
            }
        }
    }
}

print(dp[n][k])