[BaekJoon] 7579번 앱 (Kotlin) 문제 풀이 [Gold 3]

문제

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

7579번: 앱

 

어떻게 풀 것인가?

문제를 처음 봤을 때 가장 먼저 DP가 떠오르긴했다 다만, 문제는 떠오른다고 풀릴리가 없다는 것이 DP문제 아닐까....

 

그래서 문제를 차근차근 다시 읽어보니 우선적으로는 배낭 문제가 떠올랐다.

 

사실 그래서 얼마 전에 정리한 배낭 문제에 대한 포스팅을 다시 읽으며 문제를 해결했다.

(이는 아래 참고에 블로그 링크를 걸어 두었다.)

 

자 배낭문제는 조합 최적화(Combination Optimization) 문제 중 하나로, 주어진 공간(배낭)에 최대 가치를 가지는 물건들을 선택하는 문제이다.

 

그렇다면 문제에서 최대 가치는 disabled_cost된 비활성화 할때의 비용이다. 이것을 기준으로 배낭 알고리즘을 적용 활성화 되었을 때의 메모리를 DP 배열에 넣어준다면 답이 나올 것이라고 생각했다.

 

 

DP를 접근할 때 가장 좋은건 표로 보이는 것이지만, 예제에 나와있는 것으로 표를 그리면 너무 복잡해보이기 때문에

그냥 코드에서 DP 배열을 출력한 것으로 보이겠다.

 

 

와우...

위와같은 값이 DP에 저장된다면

M보다 큰 처음 값이 바로 최소의 비용을 갖는 정답이 된다.

 

풀면서 놓쳤던점

최소 비용을 구하는 것에 어려움이 많았다. 사실 배낭문제가 주어진 공간(배낭)에 최대 가치를 가지는 물건들을 선택하는 문제인데, 최소값을 물으니 처음에 접근법을 생각하기가 어려웠다.

 

이 문제를 통해 얻어갈 것

배낭문제(냅색 알고리즘)의 사용

 

내 코드 

import java.util.StringTokenizer

// 백준알고리즘 7579번 앱
fun main() = with(System.`in`.bufferedReader()) {
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val activate_cost = IntArray(n) { 0 }
    val disabled_cost = IntArray(n) { 0 }
    st = StringTokenizer(readLine())
    for (i in 0 until n) {
        activate_cost[i] = st.nextToken().toInt()
    }
    st = StringTokenizer(readLine())
    for (i in 0 until n) {
        disabled_cost[i] = st.nextToken().toInt()
    }
    val dp = Array(n + 1) { LongArray(100001) }

    for (i in 1..n) {
        for (j in dp[0].indices) {
            if (disabled_cost[i - 1] > j) {
                dp[i][j] = dp[i - 1][j]
            } else {
                dp[i][j] = (dp[i-1][j]).coerceAtLeast(dp[i-1][j-disabled_cost[i-1]]+activate_cost[i-1])
            }
        }
    }

    var answer = 0
    for (i in dp[n].indices) {
        if (dp[n][i] >= m) {
            answer = i
            break
        }
    }
    println(answer)
}

 

참고

https://superohinsung.tistory.com/191

[Algorithm] 배낭 문제(knapsack) 냅색 알고리즘