Kotlin] 백준 12865번 문제풀이

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

12865번: 평범한 배낭

 

이 문제는 아주 유명한 문제이다.

 

https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

배낭 문제 - 위키백과, 우리 모두의 백과사전

 

동적 계획법으로 풀어야하는 문제이다.

 

동적 계획법은 다음과 같은 방법론을 의미한다.

https://itstudy-mary.tistory.com/580

동적 계획법(Dynamic Algorithm)(with. Kotlin)

 

이번 케이스 같은 경우는 준서가 맬 수 있는 무게의 최대치까지 케이스를 다양하게 넣어보고, 그 중 최댓값을 고르는 것이기 때문에 상향식 접근 형식을 이용한다.

 

배낭의 접근 방식은 다음과 같다.

예제와 함께 보자.

4 7
6 13
4 8
3 6
5 12

 

준서는 총 7까지의 무게를 견딜 수 있다.

그래서 4와 3까지 넣었는데, 5를 넣는것의 가치가 더 높을 수 있지 않은가? 그럼 이를 어떻게 판단할까?

5를 넣을 수 있는 크기를 만들었을 때의 최대 가치 + 5의 가치와 현재 가치를 비교하면 된다.

이 >>5를 넣을 수 있는 크기를 만들었을 때의 최대 가치<< 를 기억하기 위해 동적 계획법을 사용하는 것이다.

그럼 이 5를 넣을 수 있는 최대 가치는 어떻게 구하느냐~

현재 무게에서 5를 뺐을때를 최대 가치라고 가정한 이전의 값을 가져오면 된다.

즉, 무게를 1부터 7(준서가 들 수 있는 최대무게)까지 설정하고, 물건을 1~4(물건의 최대 갯수)까지 하나하나 넣어보면 된다.

(w는 무게, p 는 가격이라고 하자)

 

	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
물건 1 (w 6, p 13)	0	0	0	0	0	13	13
물건 2 (w 4, p 8)	0	0	0	8	8	13	13
물건 3 (w 3, p 6)	0	0	6	8	8	13	14
물건 4 (w 5, p 12)	0	0	6	8	12	13	14

이렇게 표를 만들어서 판단해보면 된다.

 

무게 1와 2만 들 수 있을때는 아무 물건을 넣을 수 없으므로 최대 가치가 0이다.

----

무게가 3일 때는 물건 3을 넣을 수 있다. 그러나 물건 4는 넣을 수 없으므로 기존 가치를 그대로 가지고 간다.

---

무게가 4일 때를 보자.

먼저 물건 2가 무게가 4이므로, 먼저 물건 4를 넣는다.

물건 3일때를 비교해보자.

내가 물건 2를 빼고 물건 3을 넣는게 이득이냐, 물건 3만 넣는게 이득이냐. 물건 3을 넣을 수는 있나? 이걸 판단해야한다.

간단하게 판단 할 수 있다. 현재 무게에서 물건 3의 무게를 빼보면 물건 3의 자리를 만들었을때의 최대 가치를 판단 할 수 있다.

즉, 표[2][4] 와 표[2][4-3(물건 3의 무게)] + 6(물건 3의 가치) 를 비교해보면 된다.

여기서는 표[2][4]는 8, 표[4-3] + 6 = 6이므로 물건 2만 넣었을 때의 가치를 최대치로 본다.

물건 4는 넣을 수 없으므로 기존 값 그대로 간다.

---

무게가 5일때도 마찬가지이다.

표[2][5] > 표[2][2] + 6 이므로 2번 3번 물건까지는 본인의 값 그대로 가지고 간다.

4번째 출건이의 경우, 표 [3][5] = 8과, 표[3][5-5] + 12(4의 가치)를 비교했을때 물건 4만 넣는게 이득이므로 12로 변경한다.

-- -

무게가 6일때도 마찬가지이다. 

1번을 넣었을때의 가치 13

2를 넣으려 했을때 표[1][6-4] +8 = 0 + 8이므로 1번만 넣기.

3을 넣으려 했을때 표[2][6-3] + 6 = 6 + 6이므로 1번만 넣기.

4를 넣으려 했을때 표[3][6-5] + 12 = 0 + 12 이므로 1번만 넣으면 된다.

----

무게가 7일때를 보자.

1번을 넣었을 때의 가치 13.

2를 넣으려 했을때 표[1][7-4] + 8 = 8이므로 1번만 넣는다.

3을 넣으려 했을때 표[2][7-3](3번 물건과 4번 물건을 비교해서 4번을 넣었었다.) + 6 = 8 + 6이므로 14가 된다. 즉, 4번 물건을 넣은 것과 3번 물건을 넣은 것이 기존 1의 가치를 넘게 된다. 따라서, 14로 값을 변경한다.

4를 넣으려 했을때 표[3][7-5] + 12 = 12 이므로 14를 그대로 가져간다.

 

즉, 14가 최대 가치가 된다.

이런식으로 기존의 값을 메모리에 기억해두고 값을 빼서 계산을 시도한다.

이는 max((Array[이전 물건의 순서][이전 물건의 무게]), (Array[이전 물건의 순서][가지고 갈 수 있는 최대 가치 - 넣고 싶은 물건의 무게] + 넣고싶은 물건의 가치))를 지속적으로 비교하게 된다. 이렇게 계속 시도하게 되는 것을 점화식이라고 한다.

 

이제 이를 코드로 본다.

import kotlin.math.max

fun main(args: Array<String>) {
    question12865()
}

fun question12865() {
    // 물건수 + 최대 무게
    val condition = readln().split(" ").map { it.toInt() }
    val list = mutableListOf<Item>()

    for (i in 1 .. condition[0]) {
        val rawItem = readln().split(" ").map { it.toInt() }
        list.add(Item(rawItem[0], rawItem[1]))
    }

    // compareList[물건][무게]
    val compareList = arrayListOf<Array<Int>>()
    for(i in 0 .. condition[0]) {
        compareList.add(Array(condition[1] + 1){0})
    }

    var maxPrice = 0

    // 무게
    for(i in 1 .. condition[1]) {
        // 물건 넣어봄
        for(j in 1 .. condition[0]) {
            if(list[j - 1].weight > i) {
                compareList[j][i] = compareList[j-1][i]
            } else {
                compareList[j][i] = max(compareList[j-1][i-list[j-1].weight] + list[j-1].price, compareList[j-1][i])
                maxPrice = max(maxPrice, compareList[j][i])
            }
        }
    }

    println(maxPrice)

}

data class Item(
    val weight : Int,
    val price : Int
)

 

다음과 같이 Array를 이용해 2차원 배열을 선언하고, i에 무게, j에 물건 순서를 넣어 비교했다.