[ 백준 2579 ] 계단 오르기 (+ 2165: 포도주 시식) (Kotlin 풀이)

1.문제 

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

2. 입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

3. 출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

---

4. 포인트

1. 동적계획법을 통해 풀 수 있다.
2. 점화식을 세울 수 있어야한다 
   1. dp[ i ] =  dp[ i-3 ] + arr[ i-1 ] + arr[ i ]
   2. dp[ i ] =  dp[ i-2 ] + arr[ i ]
3. 경계값에 대한 예외처리를 할 수 있어야한다.

1.  

4. 계단 오르기 문제 풀이

포도주 시식 문제를 오랫동안 이해하지 못하다가 계단오르기를 풀고나서 단박에 이해가 되서

두 문제를 같이 정리하기로 했습니다.

 

계단오르기의 조건을 살펴보면 두번 연속 한칸 이동금지를 말하고 있습니다.

따라서 이를 고려하여 현재 계단까지 올 수 있는 경우의 수를 생각해보면 

• i-2 칸에서 2칸이동으로 한방에 도착
• i-3 칸에서 2칸 이동후 다시 한칸 이동해서 도착

 

dp 배열이 계단 합의 최대값을 나타내는 배열 , arr 배열이 계단 값을 나타내는 배열이라고 할때 위 경우를 점화식으로 치환하면

1. dp[ i ] =  dp[ i-3 ] + arr[ i-1 ] + arr[ i ]
2. dp[ i ] =  dp[ i-2 ] + arr[ i ]

를 얻을 수 있습니다. 두가지 경우의 수에서 더 큰 값을 갖는 것이 dp 값이 됩니다.

 

그리고 계단의 길이가 1 , 2 인 경우를 위해 dp 배열을 초기화 해줄 필요가 있습니다.

 

5. 포도주 시식 문제 풀이

포도주 시식 문제의 조건은 계단오르기 문제와 거의 유사합니다.

단 마지막칸을 반드시 밟아야한다는 조건 즉 마지막 포도주를 반드신 마셔야한다는 조건이 없습니다.

 

이 조건의 부재로 인해 i 번째 일때 i 번 째 포도주를 마시지 않는 경우의 수를 dp 값을 결정할 때 추가해주어야 합니다.

해당 경우의 수를 점화식으로 표현하면

dp [ i ]  = dp [ i-1 ]  입니다.

 

해당 경우의 수를 추가하여 점화식을 세우고 이 중 최대 값이 dp 값이 됩니다.

(와인을 마신경우 O로 안마신 경우를 X 로 표현하여 현재위치부터 2개 전 까지 마셨는지를 표현함)

 

OOX : dp [ i-1 ]

OXO : dp[ i-2 ] + arr[ i ]

XOO : dp[ i ] =  dp[ i-3 ] + arr[ i-1 ] + arr[ i ]

 

저는 이 때  OOX 를 dp[i-3] + arr[ i-2 ]  + arr[ i-1 ] 이 아닌 dp [ i-1 ] 로 표현해야하는지 의문을 가졌습니다.

그러나 이렇게 되면 OOO 가 발생하게 되고 연속성이 지켜지지 않는 것을 확인할 수 있습니다.

 

 

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val N = readLine().toInt()
    val arr = Array<Int>(N + 1) { 0 }
    val dp = Array<Int>(N + 1) { 0 }

    repeat(N) {
        arr[it + 1] = readLine().toInt()
    }

    if (N >= 1) dp[1] = arr[1]
    if (N >= 2) dp[2] = arr[2] + arr[1]


    for (i in 3..N) {
        dp[i] = max(
            max(dp[i - 1] ,dp[i - 3] + arr[i] + arr[i - 2]),
            dp[i - 3] + arr[i - 1] + arr[i]
        )
    }
    dp.forEach { println(it) }
    println(dp.maxOrNull())

}