[백준] (Swift) 2579번 - 계단 오르기 (실버3, DP)

 

⚫️ 문제

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

2579번: 계단 오르기

 

⚫️ 나의 생각

우선, 마지막 계단을 꼭 들러야한다고 한 조건이 눈에 보였다. 그럼? 결국 dp[마지막계단]을 출력했을때의 최대값을 구하면 되겠구나! 생각했다. 

이전에 dp 유형을 조금 풀어본적이 있어서 이 문제를 보고 dp배열에 어떤 것을 넣어주어야하는지 감이 왔다.

나는 dp를 이렇게 정의할것이다. 
dp[i] = i번째 계단까지 올라가는데 최대 점수

이렇게 정의를 해놓고 그림을 그려서 생각해봤다. 우선, 연달아서 세 칸을 우리는 갈 수 없다. 그래서 지금 있는 위치로 올 수 있는 방식은 다음 두가지와 같다.

1. 3번째 전 칸 → 바로앞칸 → 현재위치
2. 2번째전 → 현재위치 (두번째 전 칸에서 왔기 때문에 그 전에 어떻게 움직였든 상관없다.)

음.. 그럼 여기서 우리는 최대값을 어떻게 구할까? 앞에서 dp에 해당 칸수까지 오는데 최대값을 저장해두었다. 현재의 칸수까지 오는데 최대값을 저장하는 dp 테이블은 작은문제를 하나씩 해결해가면서 최종 위로 올라오는 방식이므로 dp 를 구현하는 두가지 방식 중 bottom-up 상향식 방식으로 볼 수 있다.  (모르는 사람은 아래 노션글을 참고해보자. 나동빈님의 강의를 보고 정리한 내용이다)

https://desert-opossum-095.notion.site/DP-8180a955db954132b9c70b05678cfa15

다이나믹 프로그래밍 (DP)

 

나는 각각의 두가지 경우의 점화식을 세웠다. 나는 결국 그 칸수까지 오는 '최대'값을 구하면 되기 때문에, 두 가지 점화식 중, max 값을 선택해서 dp 테이블에 넣어주면 된다. dp[i]는 i번재 칸에 오는 최대 점수만을 취급하기 때문에!

1. dp[i] = 점수[i] + 점수[i-1] + dp[i-3]
// 해당칸 점수 + 한칸 전 점수 + 3칸전까지 오는데 최대 점수 

2. dp[i] = 점수[i] + dp[i-2] 
// 해당칸 점수 + 2칸 전 높이까지 오는데 최대 점수

이렇게 점화식을 구할 수 있다.

여기서, 한가지 걸리는 점이 있다. 우리는 i-3까지 점화식에 넣어주어야 하므로, i 가 0, 1, 2, 3일때 따로 처리를 해주어야한다. 생각을 해보니까, 1번째 계단까지 올라오는데 최대값, 2번째 계단까지 올라오는데 최대값, 3번째 계단까지 올라오는데 최대값은 정해져있었다.

이렇게... 그래서 이 모든것들을 dp에 임의로 넣어준다.  이 모든 과정을 코드로 구현하면? 정답!

⚫️ 정답코드

import Foundation

let n = Int(readLine()!)!
var arr = [0]

for _ in 0..<n {
    arr.append(Int(readLine()!)!)
}

var dp = Array(repeating: 0, count: 301)

func solution() -> Int {
    if n == 1 {
        return arr[1]
    } else if n == 2 {
        return arr[1] + arr[2]
    } else if n == 3 {
        return max(arr[1]+arr[3], arr[2]+arr[3])
    } else {
        dp[1] = arr[1]
        dp[2] = arr[1] + arr[2]
        dp[3] = max(arr[1]+arr[3], arr[2]+arr[3])

        for i in 4...n {
            dp[i] = max(arr[i]+arr[i-1]+dp[i-3], dp[i-2]+arr[i])
        }
    }

    return dp[n]
}

print(solution())