[백준] 2579. 계단 오르기 - Python

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

2579번: 계단 오르기

---

• 생각
  • DP 
  • 계단이 1칸짜리면 1칸 오르고 끝
  • 2칸 이상일 때
    • 1번 계단 : 1번계단 오르기 점수
    • 2번 계단 : 1번계단 오르기 점수 + 2번계단 오르기 점수
    • 3번 계단 : max(1번계단 오르기 점수 + 3번계단 오르기 점수, 2번계단 오르기 점수 + 3번계단 오르기 점수)
      • 1번 -> 2번 -> 3번 : 불가능
      • 1번 -> 3번 : 가능
      • 2번 -> 3번 : 가능
    • i번( 4이상) : 두 가지 경우 중 최대값
      • 한 칸 올라서 i 인 경우 
        • 그 전에는 무조건 두 칸을 올라와야 함
      • 두 칸 올라서 i 인 경우
• 코드

from sys import stdin
input = stdin.readline

# 계단의 수
N = int(input())
# 각 계단에 쓰여 있는 점수 (stair[0] : 바닥, stair[1] : 1번 계단)
stair = [0] + [int(input()) for _ in range(N)]

# 1칸짜리 계단이면 1칸 오르면 끝
if N == 1:
    print(stair[1])
else:
    # dp[i] : i번째 계단까지 올랐을 때 얻을 수 있는 점수 최댓값
    dp = [0]*(N+1)
    dp[0] = 0
    dp[1] = stair[1]
    # 2칸으로 올라온 것/ 1칸으로 올라온 것 중 최대값
    dp[2] = max(stair[2], stair[1] + stair[2])
    for i in range(3,N+1):
    	# 2칸으로 올라온 것/ 1칸으로 올라온 것 중 최대값
        # (1칸 올라올려면 그 전에 2칸으로 올라와야함)
        dp[i] = max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i])

    print(dp[N])