[백준 28082] - 기계오리 연구(Kotlin)[골드1]

문제

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

28082번: 기계오리 연구

문제 풀이

대표적인 DP유형 중의 한 문제였던 것 같다.

나는 항상 DP 문제를 풀 때 처음에는 dp 배열을 2차원으로 접근하려고 한다.

N개의 배터리중에서 배터리를 최대 k개 사용해서 만들 수 있는 전력량의 합을 목표로 점화식을 세워보기 전에 그림으로 그려보자.

주어진 예제를 바탕으로 간단하게 그림을 그려보았다.

 

최대 k개를 사용해서 구할 수 있는 전력량의 합을 계산하기전에 배터리를 통해서 구할 수 있는 합을 간단하게 계산해 보면 위와 같다.

문제에서 의미하는 최대 k개의 배터리를 사용할 수 있다는 말의 의미는 사용할 수 있는 배터리의 종류가 최대k개라는 소리이다.

즉 2는 배터리 용량이 1인 배터리를 2개 장착해서 만들 수 있지만, 각 배터리는 한번만 사용가능하기 때문에 불가능하다.

그래서 만들 수 있는 전력량의 경우의 수는 1, 10, 11, 100, 101, 110이 된다.

 

그렇다면 우리는 해당 전력량을 구하기 위해서 dp값에 적절한 값을 저장해 몇 종류의 배터리를 사용했는지를 찾아내야 한다.

내가 생각하는 적절한 dp 배열의 의미는 다음과 같다.

dp[i][j] : i개의 배터리까지 담아서 , 전력량 j를 만드는 데 사용한 최소 배터리의 종류 

 

이렇게 dp 식을 세워서, 마지막에 dp값이 k개 이하인 j값들의 집합이 전력량의 집합일 것이다.

dp 식을 세워보니 그런 생각이 들었다. 굳이 2차원일 필요가 있을까?

dp[i-1][j] 값들을 이용해서 현재 dp[i][j]를 만드는 것이 보통의 dp 접근 방법이다.

생각해 보면 굳이 2차원으로 단계를 i로 분기하는 것이 아닌, 1차원 dp[j]만으로도, 이전 선택지의 값들을 가져올 수 있다.

 

따라서 dp 값은 

dp[i] : 전력량 i를 만드는 데 사용한 배터리의 최소 개수

로 정리가 가능하다.

 

그렇다면 점화식은 어떻게 세워야 할까?

우리가 주목해야 할 점은 하나의 배터리를 여러 번 쓰는 것이 아닌, 딱 한 번만 쓴다는 것이다.

새로운 예를 들어보자

3을 만들 수 있는 경우는 1과 2의 배터리를 조합하거나, 3의 배터리를 사용하는 것이다.

간단한 식을 세워보면 다음과 같다.

 

dp[3] = dp[1] +1  -> 2 이라는 배터리를 추가하고 남는 전력량을 구성하는데 필요한 배터리 개수

dp[3] = dp[2] + 1 -> 1 이라는 배터리를 추가하고 남는 전력량을 구성하는데 필요한 배터리 개수

dp[3] = dp[0] +1 -> 3이라는 배터리를 추가하고 남는 전력량을 구성하는데 필요한 배터리 개수

 

즉 dp[j] = dp[j - coin의 가치] + 1이 될 것이다.

당연하게도 dp의 값은 최솟값으로 갱신을 해야 하기 때문에 dp [j] = min(dp[j], dp[j-coin의 가치]+1)이 될 것이다.

그리고 우리는 배터리를 한 번만 사용할 수 있다는 사실을 알아야 한다.

예를 들어 coin의 가치가 1일 때, dp[2]는 dp[1]의 영향을 받으면 안 된다.

코드로 설명해 보면 이해가 될 것이다.

for (i in 1..n) {
	for (j in battery[i-1] .. dp.size-1) {
    	dp[j] = Math.min(dp[j], dp[j-battery[i-1]]+1)
    }
}

해당 코드일 경우, 첫 번째 배터리를 통해서 구할 수 있는 전력량을 계산할 때 dp[2]는 dp[1]의 영향을 받게 된다.

하지만 1의 배터리로 dp[2]를 만들 수 있는 경우는 존재하지 않는다.

영향을 받지 않게 할 수 있는 방법은 간단하다.

for (i in 1..n) {
    for (j in dp.size - 1 downTo battery[i - 1]) { 
        dp[j] = Math.min(dp[j], dp[j - battery[i - 1]] + 1)
    }
}

접근순서를 뒤집으면 된다.

즉 dp[2]를 먼저 계산한 후 dp[1]을 계산한다면 dp[2]는 dp[1]의 영향을 받지 않는다.

이런 문제를  처음 풀어봐서 해당 접근 방법은 떠올리기 어려웠다.

반대로 다른 유형의 문제(배터리를 여러 번 사용할 수 있는 문제)는 앞에서부터 접근해서 dp[2]가 dp[1]의 결괏값을 받아서 사용하면 될 것이다.

 

전체 코드

class Solution {

    private val br = System.`in`.bufferedReader()
    private var n = 0
    private var k = 0
    private lateinit var battery: IntArray
    private val dp = IntArray(50001) { 5000001 }
    private val sb = StringBuilder()
    private var cnt = 0
    fun run() {
        input()
        solve()
        answer()
        println(cnt)
        print(sb)
    }

    private fun input() {
        br.readLine().split(" ").map { it.toInt() }.apply {
            n = this[0]
            k = this[1]
        }
        battery = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    }

    private fun solve() {
        dp[0] = 0
        for (i in 1..n) {
            for (j in dp.size - 1 downTo battery[i - 1]) {
                dp[j] = Math.min(dp[j], dp[j - battery[i - 1]] + 1)
            }
        }
    }

    private fun answer() {
        dp.forEachIndexed { index, element ->
            if (element in 1..k) {
                cnt++
                sb.append(index).append(" ")
            }
        }
    }
}

fun main() {
    val solution = Solution().run()
}