[Swift] BOJ 2579 계단 오르기

BOJ 2579 계단 오르기

 

접근 방식

 

점화식을 세우는 DP 문제. "마지막 계단은 꼭 밟아야 한다"는 조건을 기준으로 끝에서부터 밟는 패턴을 나눔.

 

마지막 계단을 꼭 밟아야 하므로, 마지막 계단을 밟는 케이스를 보자면

 

1. O X O O (끝 계단과 바로 이전 계단을 밟음, 3연속은 안 됨, 다만 최댓값을 찾아야 하므로 전전전 칸도 포함함.)
2. ? O X O (끝 계단과 그 전전 계단을 밟음)

 

케이스 1과 2에서는 각각 끝 패턴이 위와 같이 고정됨.

 

? 자리는 어떤 것이 올지 모른다는 의미 (따라서 수식에 반영하지 않음.)

 

이를 점화식으로 바꿔 보자면(끝 칸을 n으로 가정)

 

1. (n-3) + (n-1) + n
2. (n-2) + n

 

여기서 주의할 점은 케이스 1, 2에서 가장 앞에 오는 (n-3), (n-2)가 리스트 값이 아니라 그 칸까지 누적된 dp값이라는 것임. 코드에서는 dp[i] += max(dp[i-2] + list[i], dp[i-3] + list[i] + list[i-1])로 두 패턴 중 큰 값을 고름.

 

코드

 

//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번] 계단 오르기 DP로 분류된 문제 조건 1. 계단을 오를때는 1칸 또는 2칸까지 한번에 오를수있다. 2. 연속된 3칸은 오를 수 없다. 3. 마지막 계단은 무조건 밟아야한다. 풀이 마지막 계단을 무조건 밟아야한다면 두