[Swift] 백준_계단 오르기(2579)

문제

 

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

2579번: 계단 오르기

 

 

풀이

 

아 점화식 구하는게 너무 어렵다. 

 

 

result변수를 1차원으로 둔다면 이전에 몇 개의 계단을 연속해서 올라왔는지 확인할 수 없다.

그래서 2차원배열을 이용해 result[k][1]은 연속해서 1개의 계단만 이용해서 k번째 계단까지 올라왔을때의 최대값을 의미한다. 이 말은 k-1번째 계단을 이용하지 않고 k-2번째 계단을 밟았다는 얘기이다. 그렇기때문에

result[k][1] = max(result[k-2][1], result[k-2][2]) + k번째 계단 점수가 된다.

 

result[k][2]는 연속해서 2개의 계단을 이용해서 k번째 계단까지 올라왔을때의 최대값을 의미한다. 즉, k-1계단을 밟아야하는 것이다. 하지만 이때 k-1계단까지 올라왔을 때 연속해서 2개의 계단을 이용했다면 마지막 k번째 계단의 값을 더할 수 없다. 그렇기 때문에

result[k][2] = result[k-1][1] + k번째 계단 점수가 된다.

 

두 값의 최대값을 구해주면 결과를 구할 수 있다.

import Foundation

let n = Int(readLine()!)!
var score = [0]
for _ in 0..<n {
    score.append(Int(readLine()!)!)
}
var result = Array(repeating: Array(repeating: 0, count: 3), count: n + 2)
if n == 1 {
    print(score[1])
    exit(0)
}
result[1][1] = score[1]
result[2][1] = score[2]
result[2][2] = score[1] + score[2]

for i in 2...n {
    result[i][1] = max(result[i - 2][1], result[i - 2][2]) + score[i]
    result[i][2] = result[i - 1][1] + score[i]
}
print(max(result[n][1], result[n][2]))

 

 

_____________________________________________________________________________________________________

 

 

점화식 잘 구하게 해주세요