알고리즘 - Python / 백준 - 2579번 : 계단 오르기

2579번: 계단 오르기 (acmicpc.net)

2579번: 계단 오르기

 

---

풀이

• DP 문제이므로 먼저 점화식을 찾아 정리한다.
• 연속해서 3개의 계단을 밟으면 안되고 점수를 더해야 하므로 이를 통해 점화식을 세울 수 있다.
• arrays 라는 계단별 점수 배열과 dp 배열을 동시에 이용해 각 계단별 최대 점수를 구한다.
• 각 계단마다 나올 수 있는 값의 MAX 값을 찾아 마지막 계단까지 계산해 답을 출력한다.

 

import sys

n = int(sys.stdin.readline())

arrays = [0]

for i in range(n):
  arrays.append(int(sys.stdin.readline()))

dp = [0] * (n+1)


if n == 1:
  print(arrays[1])
elif n == 2:
  print(arrays[1]+arrays[2])
else:
  dp[1] = arrays[1]
  dp[2] = arrays[2] + arrays[1]
  for i in range(3,n+1):  
    dp[i] = max(dp[i-2] + arrays[i], dp[i-3] + arrays[i] + arrays[i-1])
  print(dp[n])

---