[백준] 방 번호 (1082)(Kotlin)

원본 문제

문제 설명

이번에 VIP 회장으로 새로 부임한 백은진은 빅뱅의 위대함을 세계에 널리 알리기 위해서 사무실을 하나 임대했다.

빅뱅은 위대하기 때문에, 사무실의 번호도 되도록이면 커야 한다고 생각한다. 따라서 지금 가지고 있는 돈 전부를 가지고 방 번호를 만들려고 한다.

1층에 있는 문방구에서는 숫자를 판다. 각 숫자의 가격은 서로 다를 수 있기 때문에, 현재 가지고 있는 돈을 이용해서 만들 수 있는 가장 큰 숫자를 만들려고 한다.

예를 들어, 문방구에서 파는 숫자가 0, 1, 2이고, 각 숫자의 가격이 6, 7, 8이고, 백은진이 현재 가지고 있는 돈이 21이라면, 백은진이 만들 수 있는 가장 큰 수는 210(8+7+6=21)이다.

입력

문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 자연수이다. 예를 들어, N=4이면, 문방구에서 파는 숫자는 0,1,2,3인 것이다. 둘째 줄에 각 숫자를 사는데 드는 비용이 작은 숫자부터 주어진다. 이 비용은 50보다 작거나 같은 자연수이다. 마지막 줄에는 백은진이 현재 가지고 있는 돈이 주어진다. 돈은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 백은진이 가지고 있는 돈으로 만들 수 있는 가장 큰 수를 출력한다. 백은진이 가지고 있는 돈은 적어도 숫자 하나는 살 수 있기 때문에, 답은 항상 존재한다.

0을 제외하고 0으로 시작하는 수는 없다.

테스트 케이스

입력	출력
3 6 7 8 21	210
3 5 23 24 30	20
10 1 1 1 1 1 1 1 1 1 1 50	99999999999999999999999999999999999999999999999999
2 1 50 50	1
2 2 1 10	1111111111
1 10 20	0
3 6 7 8 6	0

문제 풀이1 (DFS - 실패)

import java.util.*

var N = 0
var costs = intArrayOf()
var maxLength = 0
val result = mutableSetOf<String>()

fun main() = with(Scanner(System.`in`)) {
    N = nextInt()
    costs = IntArray(N) { nextInt() }
    val asset = nextInt()

    for (i in N - 1 downTo 1) {
        dfs(i, asset - costs[i], i.toString())
    }

    println(result)
    println(result.maxWith(::compare))
}

fun compare(o1: String, o2: String): Int {
    return if (o1.length == o2.length) {
        var result = 0
        for (i in o1.indices) {
            if (o1[i] != o2[i]) {
                result = o1[i] - o2[i]
                break
            }
        }
        result
    } else {
        o1.length - o2.length
    }
}

fun dfs(num: Int, asset: Int, roomNum: String) {
    if (asset <= 0 && roomNum.length > maxLength) {
//        println("result : ${roomNum}, result.length : ${roomNum.length}")
        maxLength = roomNum.length
        result.add(roomNum)
        return
    }

    for (i in num downTo 0) {
        val remainAsset = asset - costs[i]
        if (remainAsset >= 0) {
            dfs(i, remainAsset, roomNum + i.toString())
        } else {
            dfs(i - 1, remainAsset, roomNum)
        }
    }
}

문제 풀이2 (DP - knapsack)

iimport java.util.Scanner

var N = 0
var costs = arrayOf<Pair<Int, Int>>()
val list = mutableListOf<Pair<String, Int>>()

fun main() = with(Scanner(System.`in`)) {
    N = nextInt()
    costs = Array(N) { Pair(it, nextInt()) }.sortedBy { it.second }.toTypedArray()

    val start = costs.filter { it.first != 0 }.sortedBy { it.second }.toTypedArray()
    val asset = nextInt()

    for ((num, value) in start) {
        if (asset - value >= 0) list.add(findMaxLengthNum(asset - value, num.toString()))
    }

    if (list.isEmpty()) {
        println(0)
        return
    }

    val maxLengthNum = list.maxWith(Comparator { o1, o2 ->
        if (o1.first.length == o2.first.length) {
            var result = 0
            for (i in o1.first.indices) {
                if (o1.first[i] != o2.first[i]) {
                    result = o1.first[i] - o2.first[i]
                    break
                }
            }
            result
        } else {
            o1.first.length - o2.first.length
        }
    })!!

    val result = maxLengthNum.first[0] + findMax(maxLengthNum.first.length, 1, maxLengthNum.first, maxLengthNum.second)
    println(result)
}

fun findMax(depth: Int, index: Int, roomNum: String, asset: Int): String {
    if (depth == index) return ""

    var indexedNum = roomNum[index]
    var indexedNumCost = costs.find { it.first == roomNum[index].toInt() - 48 }!!.second
    var remainedAsset = asset

    for ((num, value) in costs) {
        if (asset + indexedNumCost - value >= 0 && indexedNum.toInt() - 48 < num) {
            indexedNum = num.toString()[0]
            remainedAsset = asset + indexedNumCost - value
        }
    }

    return indexedNum + findMax(depth, index + 1, roomNum, remainedAsset)
}

fun findMaxLengthNum(asset: Int, startNum: String): Pair<String, Int> {
    var remainedAsset = asset
    var maxLengthNum = startNum

    for ((num, value) in costs) {
        if (remainedAsset - value >= 0) {
            val quotient = asset / value
            remainedAsset -= (value * quotient)
            repeat (quotient) {
                maxLengthNum += num
            }
        }
    }

    return Pair(maxLengthNum, remainedAsset)
}