[백준 1106] - 호텔(Kotlin)[골드5]

문제

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

1106번: 호텔

 

문제 풀이

처음에 그리디인 줄 알고 접근했다가, 도저히 그리디로 할 수가 없어서 DP로 접근방식을 수정했다.

DP문제에서 가장 중요한 점은 DP 배열을 어떤 식으로 설계하느냐이다.

다양한 방법으로 설계할 수 있지만, 문제에서는 최소한의 비용으로 목표 인원수를 모을 수 있느냐에 초점을 맞추기 때문에

DP배열의 index를 비용으로 잡았다. 그 부분이 나중에 최소 비용을 찾기 편하다고 생각했다.

 

DP [n]은 n원을 사용해서 모을 수 있는 최대의 고객수이다.

DP 배열을 선언하고, 최대 사이즈를 정하는데 꽤 많은 고민을 했다.

최대 경우의 수를 생각해 봤다.

C의 최댓값은 1000이고, 

최악의 경우는 홍보비용이 100이고, 그로 인해 모을 수 있는 고객의 수가 1명일 경우

1000명을 모으기 위해서는 100*1000이라는 비용이 발생합니다.

따라서 최악의 경우의 수에 근거해서 최대 크기는 100001로 잡았습니다.

 

DP 배열을 업데이트하는 과정은 다음과 같습니다.

DP[i] = max(DP[i],DP[i-l.first]+l.second)

DP배열은 도시를 돌면서 계속해서 업데이트합니다. 

항상 DP [i]에는 i 비용을 사용하면서 모을 수 있는 최대의 고객수가 들어가야 합니다.

DP [i]와 DP [i-l.first]+l.second를 비교하는 이유는 다음과 같습니다.

현재 DP [i]에는 이전 도시까지의 최대 고객수가 들어가 있습니다. 

따라서 현재 도시에서 홍보하는 데 사용하는 비용을 빼고, 그때의 DP값과 홍보로 모을 수 있는 사람의 수를 더하면 

현재 도시에서의 DP값이 되고, 이전의 DP값과 현재 DP값을 비교해서 업데이트해주는 것입니다.

 

이렇게 모든 DP 배열에 대해서 업데이트를 한 후, DP값이 처음으로 C이상이 되는 index가 최소비용일 것입니다.

 

코드

package Baekjoon.DP.`1106`

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

class `1106` {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var C = 0
    var list : ArrayList<Pair<Int,Int>> = ArrayList()
    var DP : Array<Int> = Array(1000 * 100+1 , { 0 })
    init{
        input()
        solution()
    }
    fun input(){
        var line = br.readLine().split(" ")
        C = line[0].toInt()
        var N = line[1].toInt()
        for(i in 0 until N){
            line = br.readLine().split(" ")
            list.add(Pair(line[0].toInt(),line[1].toInt()))
        }
    }
    fun solution(){ //가장 ㅂ비율이 좋은 도시로 최대한 쪼개고.
        for(l in list){ //k명을 뽑는데 최소한의 비용을 결정하자.
            for(i in 0 until DP.size){ //i원을 사용해서 뽑을 수 있는 최대의 고객수를 결정하자
                if(i-l.first>=0){ //비용이 넘는다면
                    DP[i] = max(DP[i],DP[i-l.first]+l.second)
                }
            }
        }
        for(i in 0 until DP.size){
            if(DP[i]>=C){
                print(i)
                break
            }
        }
    }
}
fun main(){
    val solution = `1106`()
}