[백준] 호텔 (1106)

문제 설명

백준 1106번 문제 링크

문제 풀이 참고

입력 및 출력

» 입력

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

» 출력

첫째 줄에 문제의 정답을 출력한다.

예제 입출력(테스트케이스)

입력	출력
12 2 3 5 1 1	8
10 3 3 1 2 2 1 3	4
10 10 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10	10
100 6 4 9 9 11 3 4 8 7 1 2 9 8	45

문제 풀이(KOTLIN) 1

import kotlin.math.max

fun main() {
    val (cost, cities) = readLine()!!
        .split(" ")
        .map { it.toInt() }

    var dp = Array<Int>(100001) { 0 }
    val list = mutableListOf<Pair<Int, Int>>()

    repeat(cities) {
        val (totalCost, totalCities) = readLine()!!
            .split(" ")
            .map { it.toInt() }
        list.add(Pair(totalCost, totalCities))
    }

    for (i in list.indices) {
        for (j in 1 ..100000) {
            if (j - list[i].first >= 0) {
                dp[j] = max(dp[j], dp[j - list[i].first] + list[i].second)
            }
        }
    }

    for (i in 1..100000) {
        if (dp[i] >= cost) {
            println(i)
            break
        }
    }
}