[백준] 2579 계단 오르기 - 파이썬

2579번: 계단 오르기

---

* 무조건 첫 번째 계단을 밟지 않아도 됨

import sys
n = int(input())
s = [int(sys.stdin.readline()) for _ in range(n)]

dp = []
for i in range(2):
  dp.append(sum(s[:i + 1])) 
if n >= 3:
  dp.append(max(s[0] + s[2], s[1] + s[2]))
for i in range(3, n):
  dp.append(max(dp[i - 3] + s[i - 1] + s[i], dp[i - 2] + s[i]))
print(dp.pop())

6~7행: 계단이 한 칸이거나 두 칸일 경우를 위한 코드인데 계단이 한 칸 들어올 경우에도 dp가 크기가 2가 되고, 첫 번째 계단의 값이 두 번 중복해서 들어가게 됨. 오류는 나지 않지만 좋은 코드는 아닌 것 같아서 나중에 수정할 예정.

s는 계단의 값들을 담아둔 배열, dp는 각 계단마다의 최대값을 담아둔 배열이다. 

dp[0]은 0번째 계단까지의 최대합이므로 당연히 s[0]의 값이고,

dp[1]은 1번째 계단까지의 최대합이므로 s[0]과 s[1]의 합이다. 

dp[2]같은 경우는 문제의 조건에 따라 연속된 3칸의 계단을 밟으면 안 되기 때문에 

dp[0] + dp[2] 혹은 dp[1] + dp[2] 중에서의 최대값이다. 

 

만일 s = [10, 20, 1]이라고 하면 dp = [10, 30, 21]이 되고 정답은 21이 된다.

마지막 계단을 꼭 밟아야 하기 때문에 dp[1]의 값이 더 크더라도 dp[2]가 정답이 된다.

 

마지막 계단을 기준으로 전 계단에서 올라온 경우와 전전 계단에서 올라온 경우가 있다. 

case1) 전 계단에서 올라왔다면 연속 세 개의 계단을 밟을 수 없으므로 아래 그림처럼 무조건 계단 하나를 건너 뛰어야 한다.

dp[2] + s[3] + s[4] = 35 + 10 + 20 = 65

 

case2) 전전 계단에서 올라온 경우는 상관없다. 그냥 전전 칸의 최대합과 마지막 계단 값을 더해주면 된다.  

dp[3] + s[5] = 55 + 20 = 75

 

case1과 case2 중 최대 값을 dp에 넣어주고 출력해주면 끝이다.