백준 21317 징검다리 건너기 Kotlin (dp)

문제 출처 : https://www.acmicpc.net/problem/21317

21317번: 징검다리 건너기

 

문제

심마니 영재는 산삼을 찾아다닌다.

산삼을 찾던 영재는 N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다.

마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가 있다.

점프의 종류에는 현재 위치에서 다음 돌로 이동하는 작은 점프, 1개의 돌을 건너뛰어 이동하는 큰 점프, 2개의 돌을 건너뛰어 이동하는 매우 큰 점프가 있다.

각 점프를 할 때는 에너지를 소비하는데, 이 때 작은 점프와 큰 점프시 소비되는 에너지는 점프를 하는 돌의 번호마다 다르다.

매우 큰 점프는 단 한 번의 기회가 주어지는데, 이때는 점프를 하는 돌의 번호와 상관없이 k만큼의 에너지를 소비한다.

에너지를 최대한 아껴야 하는 영재가 산삼을 얻기 위해 필요한 에너지의 최솟값을 구하여라.

영재는 첫 번째 돌에서부터 출발한다.

입력

첫 번째 줄에는 돌의 개수 N이 주어진다.

N - 1개의 줄에 걸쳐서, 1번 돌부터 N - 1번 돌 까지의 작은 점프를 하기 위해 필요한 에너지, 큰 점프를 하기 위해 필요한 에너지가 주어진다.

마지막 줄에는 K가 주어진다.

출력

산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다.

제한

• 1 ≤ N ≤ 20
• 작은 점프, 큰 점프 시 필요한 에너지와 K는 5,000을 넘지않는 자연수이다.

알고리즘 분류

• 다이나믹 프로그래밍
• 브루트포스 알고리즘
• 백트래킹

풀이

N값이 작아서 완전 탐색해도 되지만 본인은 dp로 풀었다.

우선 입력 값을 제대로 이해해야 한다.

n = 5

1번 돌에서 작은 점프에 필요한 값 1, 큰 점프에 필요한 값 2

2번 돌에서 작은 점프에 필요한 값 2, 큰 점프에 필요한 값 3

3번 돌에서 작은 점프에 필요한 값 4, 큰 점프에 필요한 값 5

4번 돌에서 작은 점프에 필요한 값 6, 큰 점프에 필요한 값 7

k = 4  // 매우 큰 점프에 필요한 값

 

dp[i][j] = 매우 큰 점프를 쓰거나 쓰지 않고 (1/0) i 번 돌에 도달했을 때 소비한 최소 에너지

 

우선 매우 큰 점프가 없다고 생각하면 아래의 점화식으로 간단하게 구현할 수 있다.

dp[i+1][0] = dp[i][0] + bridge[i].first vs dp[i+1][0]

dp[i+2][0] = dp[i][0] + bridge[i].second vs dp[i+2][0]

 

문제는 매우 큰 점프가 있을 때다.

현재 i에서 3칸 다음인 i+3 번 돌에 도착하는 경우는 어떤 경우가 있을까

매우 큰 점프를 앞에서 이미 쓴 경우 i+2 번 돌에서 작은 점프 == dp[i+2][1] + bridge[i+2].first

매우 큰 점프를 앞에서 이미 쓴 경우 i+1 번 돌에서 큰 점프 == dp[i+1][1] + bridge[i+1].second

i 번 돌에서 매우 큰 점프를 하는 경우 == dp[i][0] + k 

따라서 다음과 같은 점화식을 세울 수 있다.

dp[i+3][1] = (dp[i+2][1]+bridge[i+2].first).coerceAtMost(dp[i+1][1]+bridge[i+1].second)
dp[i+3][1] = dp[i+3][1].coerceAtMost(dp[i][0]+k)

 

dp의 크기를 n + 4로 하여 outOfBounds를 방지하자.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun main() = with(System.out.bufferedWriter()) {
    //input
    val INF = 1_000_000
    val n = getInt()
    val bridge = Array(n + 4) { Pair(0, 0) }
    val dp = Array(n + 4) { IntArray(2) { INF } }
    for (i in 1 until n) {
        val (a, b) = getIntList()
        bridge[i] = Pair(a, b)
    }
    val k = getInt()
    //solve
    dp[1][0] = 0
    for(i in 1 .. n){
        dp[i+1][0] = dp[i+1][0].coerceAtMost(dp[i][0] + bridge[i].first)
        dp[i+2][0] = dp[i+2][0].coerceAtMost(dp[i][0] + bridge[i].second)
        dp[i+3][1] = (dp[i+2][1]+bridge[i+2].first).coerceAtMost(dp[i+1][1]+bridge[i+1].second)
        dp[i+3][1] = dp[i+3][1].coerceAtMost(dp[i][0]+k)
    }
    //output
    write("${dp[n][0].coerceAtMost(dp[n][1])}")
    close()
}