[백준/Swift] 2579번: 계단 오르기

 

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

2579번: 계단 오르기

 

DP는 그 안에서도 굉장히 많은 유형이 있다고 생각한다.

이 문제는 DP 기본 문제 중 하나라고 생각하는데, 조건이 추가된 것도 그렇고, 작은 문제에서 큰 문제로 가는 방식도 그렇고.

정말.. 어렵다~ DP

 

우선 문제를 정리해 보자면, N번째 계단에 최댓값으로 올라가야 한다.

이동 방법은 

1) 1칸 이동

2) 2칸 이동

중요한 게 바로 조건! 연속 3칸을 밟으면 안 된다.

 

DP는 N보다 작은 애들의 결과로 N의 답을 도출해 내는 것이다. 그러므로 앞에서부터 차근차근 진행해야 한다.

작은 문제의 값을 저장해서(memorization) 더 큰 문제에 사용할 것이므로 dp라는 배열에 넣을 것이다.

그런데 여기서 dp 배열을 통해 이동 방법을 나눌 수 있다. (1칸 이동, 2칸 이동) → 2차원 배열 dp[0][i], dp[1][i]

i라는 계단 칸에 도착할 때, 1칸씩 이동한 것과 2칸씩 이동한 것은 결괏값이 다를 것이므로 그중 최댓값을 구해야 한다.

그래서 나중에 이 2차원 배열의 행의 값의 최댓값을 결과로 출력할 것.

 

dp의 구성은

- dp[0][i]: i-1번째 칸을 밟고, i번 도착 (1칸 이동)

- dp[1][i]: i-1번째 칸을 안 밟고, i번 도착 (2칸 이동)

 

위에서도 말했지만 연속 3칸을 밟으면 안 된다! 이게 가장 이 문제의 핵심인데

아래의 그림처럼 그려봤다. i칸에 도착할 때의 경우의 수를 그린 것인데 총 3가지 방법이 나온다.

(i-3, i-2, i), (i-4, i-2, i), (i-3, i-1, i)

정리하면,

i-1번을 밟으면

i-2를 무조건 밟을 수 없기 때문에(연속 3칸 불가) 1가지 방법 밖에 안됨 -> i-1칸에서 1칸 이동

i-2번을 밟으면

이 조건은 무조건 i-1을 못 밟는 것으로 -> i-2칸에서 i칸으로 2칸 이동

i-3번을 밟거나 안 밟거나 경우가 나온다. 여기서 또, i-3번을 밟으면 i-4번은 밟을 수 없다.

-> (i-3칸에서 i-2칸으로 1칸 이동, i-4칸에서 i-2칸으로 2칸 이동)

 

이런 식으로 진행하면 된다.

점화식으로 나타내면

dp[i][1] = max(dp[i-2][0], dp[i-2][1]) + stair[i]
dp[i][0] = dp[i-1][0] + stair[i]

 

[전체 코드]

import Foundation

/*
 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임
 각각의 계단에는 일정한 점수가 쓰여있는데, 계단을 밟으면 그 계단에 쓰인 점수 얻음
 1. 한번에 한계단 혹은 두계단
 2. 연속된 3개의 계단을 모두 밟으면 안됨. 시작점은 계단 아님
 3. 마지막 도착 계단은 반드시 밟아야 됨
 최대 점수 출력
 */

//input
let n = Int(readLine()!)!
var stair = [0]
var dp = [[Int]](repeating: [Int](repeating: 0, count: 2), count: n+2)
for _ in 0..<n {
    stair.append(Int(readLine()!)!)
}

//dp[0][i]: i-1번 밟고, i번 도착
//dp[1][i]: i-1번 안밟고, i번 도착

//초기화
dp[1][1] = 0
dp[1][0] = stair[1]
if n == 1 {
    print(stair[1])
}else if n == 2 {
    print(stair[1] + stair[2])
}else {
    dp[2][1] = stair[2]
    dp[2][0] = stair[2] + stair[1]
    for i in 3...n {
        dp[i][1] = max(dp[i-2][0], dp[i-2][1]) + stair[i]
        dp[i][0] = dp[i-1][0] + stair[i]
    }
    print(max(dp[n][0], dp[n][1]))
}

 

 

일단 작은 수부터 차례대로 쭉 해보면서 공통점 찾는 게 관건이다.

어렵군요 ;0;