[Swift] BOJ 2579 계단 오르기

 BOJ 2579 계단 오르기

 

✅ 점화식을 이용한 DP문제였다.

나동빈 책을 공부하면서 비슷한 문제를 해결하려는 노력을 했었는데, 진짜 너무나도 어려웠다.

여기서는 점화식을 세우기 위해 문제의 마지막 조건의 초점을 맞추는데,

 

마지막 계단은 꼭 밟아야 한다. 이 문장을 기준으로 점화식을 설계해보자!!!!

 

마지막 계단을 꼭 밟아야 하므로, 마지막 계단을 밟는 케이스를 보자면1. O X O O (끝 계단과 바로 이전 계단을 밟음, 3연속은 안된다, 근데 최댓값을 찾아야 하므로 전전전칸도 포함한다.)2. ? O X O(끝 계단과 그 전전 계단을 밟음)

케이스 1에서는 끝 패턴이 저걸로 고정 

케이스 2에서는 끝 패턴이 저렇게 고정 

? 자리는 어떤게 올지 모른다는 말 -> 따라서 수식에 반영하지 않는다.

 

이를 점화식으로 바꿔보자면(끝 칸을 n으로 가정)1. (n-3) + (n-1) + n2. (n-2) + n그러나 여기서 주의할 점은 케이스 1과2에서 가장 앞에 오는 경우는 dp값 즉, 누적된 값을 갖고 있다는 말이다.

 

dp를 공부하면서 점화식을 세워야 한다. 더 노력하자!

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

struct b2579 {
    
    static func run() {
        // DP를 이용하여 풀어야 합니다.
        let input: Int = Int(readLine()!)!
        var list = [Int]()
        for _ in 0..<input {
            list.append(Int(readLine()!)!)
        }
        
        var dp = [Int](repeating: 0, count: 301)
        if input >= 1 {
            dp[0] = list[0]
        }
        if input >= 2 {
            dp[1] = list[0] + list[1]
        }
        if input >= 3 {
            dp[2] = max(list[0] + list[2], list[1] + list[2])
            for i in 3..<list.count {
                dp[i] += max(dp[i-2] + list[i] , dp[i-3] + list[i] + list[i-1])
            }
        }
        
        
        print(dp[input-1])
    }
}

 

 

 

(참고)
https://kwanghyuk.tistory.com/4

[백준 2579번] 계단 오르기