백준 - 평범한 배낭(kotlin) 못풀었음

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/12865

 

[문제 설명]

2차원 dp를 활용한 문제. 스스로 못풀었음.

 

[접근 방법]

처음엔 대부분에 난이도가 낮은 동적 프로그래밍 문제처럼 일차원 배열을 만들어서 동적프로그래밍을 구현하려 했다.

예를 들어, 1kg 3원 1kg 2원 2kg 5원 2kg 4원이라면

1kg는 3원이 최댓값, 2kg는 5원이 최댓값 그리고 이 둘을 가지고 배낭을 구성하는 식으로 풀려고 했다.

그러나, 이는 말이 안된다. 무게당 1개의 물품을 고르라는 조건이 있으면 모를까.

 

그래서 각 물품이 들어가냐 마냐에 따라 문제가 갈린다고 생각했다.

이는 가장 간단한 완전탐색을 생각하게 했다. 허나, 이 경우에 시간 복잡도는 O(2^n)으로 최악의 경우 2^100의 연산이 나온다.

따라서 이도 정답이 될 수 없다.

 

결국, 문제를 내 힘으로 풀지 못했고, 답지를 봤다.

답지를 보고 느낀 건데 확실히 dp에  위엄을 느끼게 됐다.

나는 넣었냐 뺏냐 같이 선택 문제가 나오면 dp를 생각하지 못하고, 완전탐색으로 푸는 경향이 있다.

왜냐? 그냥 단순히 해석했을 때, 넣었냐 뺏냐 -> 조합 -> 완전탐색 이러한 알고리즘이 돌아가는 버릇이 있다.

물론 완전탐색을 써야 맞는 문제도 있다.

 

그러나, 위 문제처럼 최적의 해가 있는 문제는 그럴 필요가 없다.

예를 들어, 10kg를 견딜 수 있는 가방이 있다고 하자, 남은 물건은 6kg짜리 물건이다.

이를 보면, 단순하게 6kg를 넣을까 말까로 생각할 수 있다.

 

그렇다면 물건을 넣는 경우와 넣지 않는 경우를 구현해보자.

물건을 넣지 않는 경우는 간단하다. 이번 물건 이전까지 선택한 경우의 가치 + 0. 즉, 이전까지의 합이 넣지 않는 경우다.

물건을 넣는 경우는 어떻게 생각할까? 정답은 4kg인 가방이 최대한 담을 수 있는 가치 + 6kg짜리 물건의 가치가 정답이다.

왜냐? 6kg짜리 물건을 담으려면 최소 6kg의 공간이 필요하다.

따라서, 4kg로 최대한 담을 수 있는 경우 + 6kg 물건의 무게가 된다.

사실, 0kg~4kg 가방들의 가치 중에 최대이지만, 당연하게도 0~3kg보다는 4kg짜리 가방에 더 많은 물건을 담을 수 있으므로 4kg의 가방을 기준으로 잡는 것이다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val k = st.nextToken().toInt()
    val dp = Array(n + 1) { IntArray(k + 1) }

    // first : weight, second :
    val products = Array<Product?>(n + 1) { null }
    repeat(n) { idx ->
        st = StringTokenizer(br.readLine())
        products[idx + 1] = Product(weight = st.nextToken().toInt(), price = st.nextToken().toInt())
    }

    for (col in 1..k) {
        for (row in 1 .. n) {
            if (products[row]!!.weight > col) {
                dp[row][col] = dp[row - 1][col]
                continue
            }
            dp[row][col] = dp[row - 1][col].coerceAtLeast(dp[row - 1][col - products[row]!!.weight] + products[row]!!.price)
        }
    }

    println(dp[n][k])
}

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