[다이나믹 프로그래밍] 백준 실버3 2579번: 계단 오르기(Swift)

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

2579번: 계단 오르기

풀이과정

문제를 정리하면,

계단마다 점수가 있다.

계단은 1칸 혹은 2칸씩 오를 수 있다.

하지만, 연속된 세 개의 계단을 모두 밟을 수는 없다.

이때 얻을 수 있는 점수의 최댓값을 구해야 한다.

중요한 키워드만 정리해 보았다.

해당 문제는 DP를 활용하여 풀 수 있다.

각 계단을 올랐을 때 포인트의 최댓값을 알고 있으면 해당 포인트에 앞으로 오를 계단의 포인트를 더해주면 해결할 수 있다.

계단 수가 1번부터 3번까지는 직접 계산할 수 있다.

dp[1] = points[1]
dp[2] = points[1] + points[2]
dp[3] = max(points[1] + points[3], points[2] + points[3])

4번째 계단의 경우,

1번 -> 3번 -> 4번 경우와 // 1번 케이스

1번 -> 2번 -> 4번의 경우가 있다 // 2번 케이스

1번 케이스의 경우 1번 계단까지 도달한 점수 + 3번, 4번 계단의 점수를 계산해 주면 된다.

2번 케이스의 경우 1과 2가 연속되었기 때문에 2번 계단까지 도달한 점수 + 4번 계단의 점수를 계산해 주면 된다.

이제 이를 코드로 작성해 보면

let n = Int(readLine()!)!

var points: [Int] = [0]
var dp = Array(repeating: 0, count: n + 1)

for _ in 0..<n {
  let point = Int(readLine()!)!
  points.append(point)
}

if n == 1 {
  print(points[1])
} else if n == 2 {
  print(points[1] + points[2])
} else if n == 3 {
  let result = max(points[1] + points[3], points[2] + points[3])
  print(result)
} else {
  dp[1] = points[1]
  dp[2] = points[1] + points[2]
  dp[3] = max(points[1] + points[3], points[2] + points[3])
  
  for i in 4...n {
    dp[i] = max(points[i] + points[i-1] + dp[i-3], points[i] + dp[i-2])
  }
  print(dp[n])
}

 

위와 같이 코드로 작성할 수 있다.