[백준] 2579 (계단 오르기)

#1 알고리즘

#1-2

계단을 오르는 사람 입장에선, 땅에서부터 시작해 1칸 또는 2칸을 오르는 선택지만이 존재한다. 따라서 위와 같은 재귀함수의 형태를 잡을 수 있다. 

 

#1-2

또, 문제의 조건에서 밟은 계단이 3연속되면 안된다고 했으므로 해당 조건을 고려해 과 같이 구조를 짤 수 있다.

 

#1-3

하지만, stepOnStair()는 재귀호출을 2번 하므로 계단이 많아지면 처리량이 매우 커져버린다. 따라서, 재귀호출 과정에서 가지치기를 할 필요가 있다. 경우 a와 경우 b를 비교해보면, 4번 계단에서 b가 a보다 더 큰 점수를 가진다. 2579번 문제는 마지막 계단까지 누적된 최고 점수를 구하는 것이기에, 경우 b가 존재하는 이상 경우 a와 a에서 파생될 수 많은 경우의 수는 계산할 필요가 없다.

또, 경우 b와 c를 비교해보면, 각각의 경우 4번 계단까지 누적된 점수가 같다. 하지만, c는 4번 계단의 시점에서 바로 뒤 3번 계단을 밟았기에, 777점이나 하는 5번 계단을 밟을 수 없다. 반면, b는 밟을 수 있다. 이와같이, 단순히 어떤 계단까지 누적된 점수만 비교할 게 아니라 그 계단이 뒤에서부터 얼마나 연속되었는지까지 고려해서 가지치기를 해야 한다.

 

#1-4

어떤 계단 번호 a와 continuous값 b에 대해 a까지 가는데 누적된 점수가,
maxAccumulatedScoreOnStair[Pair<a, b>]의 Value보다 같거나 작다면, 함수를 종료해 가지치기(재귀호출이 되지 않게)한다.

 

#2 코드 - 코틀린

var maxStairIndex = 0
lateinit var scores : Array<Int>
val maxAccumulatedScoreOnStair : HashMap<Pair<Int, Int>, Int> = HashMap()

fun main() {
    maxStairIndex = readln().toInt()
    scores = Array(maxStairIndex + 1) { 0 } // 땅까지 포함하기에 +1
    for (i: Int in 1..maxStairIndex) {
        scores[i] = readln().toInt()
    }

    stepOnStair(0, 0, 0)

    println(
        maxOf(
            (maxAccumulatedScoreOnStair[Pair(maxStairIndex, 0)] ?: 0),
            (maxAccumulatedScoreOnStair[Pair(maxStairIndex, 1)] ?: 0),
            (maxAccumulatedScoreOnStair[Pair(maxStairIndex, 2)] ?: 0)
        )
    )
}

fun stepOnStair(lastSteppedStair : Int, scoreExceptLastStep : Int, continuous : Int) {
    // (함수 종료) 연속된 계단 3개를 밟은 경우
    if(3 <= continuous) {
        return
    }

    // (함수 종료) 마지막 계단를 지나쳐 밟은 경우
    if(lastSteppedStair > maxStairIndex) {
        return
    }

    // 현재 계단 제외 축적된 점수 + 현재 밟고 있는 계단의 점수
    val includeLastStepScore = scoreExceptLastStep + scores[lastSteppedStair]

    // 현재까지 축적된 점수가 최고점이면 갱신. 이 때, 계단 정보 뿐만 아니라, 현재 계단에서 바로 뒤에 밟은 계단들이 얼마나 연속되었는지의 정보까지 Key로 취급
    if((maxAccumulatedScoreOnStair[Pair(lastSteppedStair, continuous)] ?: 0) <= includeLastStepScore) {
        maxAccumulatedScoreOnStair[Pair(lastSteppedStair, continuous)] = includeLastStepScore

    // (함수 종료) 같은 Key인데 Value가 더 작다면, 이 시점에서 미래에 어떤 재귀호출을 하든 최고점 도출에는 아무런 의미가 없으므로 함수 종료. (가지치기)
    } else {
        return
    }

    // (함수 종료) lastSteppedStair가 마지막 계단인 경우
    if(lastSteppedStair == maxStairIndex) {
        return
    }

    // 재귀호출
    stepOnStair(lastSteppedStair + 1, includeLastStepScore, continuous + 1)
    stepOnStair(lastSteppedStair + 2, includeLastStepScore, 1)
}