[백준] (Swift) 2579번 - 계단 오르기 (dp 기본문제, 실버3)

 

🟠 문제링크

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

2579번: 계단 오르기

 

🟠 문제 풀이 아이디어

가장 기초적인 dp 문제중 하나였다. 하지만 가장 중요한것은, 생각을 반대로해야한다는 것이었다.

"처음부터 계단을 어떻게 올라가지?" 생각보다는, "최종 도착지기준으로 봤을때, 어디서 올라왓찌?"를 고려해봐야한다는 것이다.
연속으로 3칸의 계단을 밟을 수가 없기 때문에, 도착지 기준으로 올라올 수 있는 방법은 아래 그림처럼 딱 두가지 방법이다.

이렇게 dp 점화식을 유도해냈다.

dp점화식에 내가 한 실수를 적어두었다. 적어둔 것 처럼, 그림에서 ①번 루트인 경우에는, dp[n-3] + dp[n-1] 로 해버리면, 누적된 합을 두번이나 더해주는 것과 같아진다. 그래서 dp[n-3]에다가, 나머지 두번은 arr (계단 각각의 값)을 더해준 것을 합쳐줘야한다!!

나는 여기서 dp[n-3] + dp[n-1] + arr[n] 이라고 작성해서 답이 나오지 않아 꽤 오랫동안 고민했다 😅

 

🟠 정답 코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/2579_%EA%B3%84%EB%8B%A8%EC%98%A4%EB%A5%B4%EA%B8%B0/main.swift

GitHub - deslog/Algorithm

let n = Int(String(readLine()!))!
var arr = [0]
for _ in 0..<n {
    arr.append(Int(String(readLine()!))!)
}

var dp = Array(repeating: 0, count: n+1)

// main
dp[0] = 0
for i in 1..<n+1 {
    if i == 1 {
        dp[1] = arr[1]
    } else if i == 2 {
        dp[2] = arr[1] + arr[2]
    } else if i == 3 {
        dp[3] = max(arr[3]+arr[1], arr[3]+arr[2])
    } else {
        dp[i] = max(arr[i] + arr[i-1] + dp[i-3], arr[i] + dp[i-2])
    }
}

print(dp[n])