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

문제 : https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

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

www.acmicpc.net

풀이

import java.util.*
import kotlin.math.max

fun main() = with(Scanner(System.`in`)){
    val n = nextInt()
    val a = Array(n+1){0}
    val dp = Array(n+1){0}

    for(i in 1 until a.size){
        a[i] = nextInt()
    }

    for(i in 1 until dp.size){
        when (i) {
            0 -> dp[i] = 0
            1 -> dp[i] = a[1]
            2 -> dp[i] = a[1] + a[2]
            /**
             * 1. 1번 연속으로 밟는 경우
             * 2. 2번 연속으로 밟는 경우
             */
            else ->{
                dp[i] = max((a[i] + dp[i-2]),(a[i]+a[i-1]+dp[i-3]))
            }
        }
    }

    println(dp[n])
}

2021.11.01 - [알고리즘, 자료구조/백준] - [백준] 2156. 포도주 시식 (Kotlin)

[백준] 2156. 포도주 시식 (Kotlin)

문제 : https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시

hanyeop.tistory.com

위 문제와 상당히 유사한 문제이다.

포도주 시식 문제에서는 마시지 않고 건너뛰는 선택지가 있었지만, 계단 오르기는 앞의 계단을 오르느냐, 그다음 계단을 오르느냐의 선택지밖에 없다.

DP에 현재 위치에 도달했을 때 가장 많이 얻을 수 있는 점수를 저장한다.

그리고 계단을 3번 연속 올라갈수 없으므로 1개, 2개 계단에는 전부 오르는게 최대의 경우다.

3번째 계단부터