백준 알고리즘 파이썬(Python) 2579번 계단오르기

---

우선 문제의 세 가지 규칙 중 마지막 규칙을 주의 깊게 봐야 한다.

마지막 도착 계단은 반드시 밟혀있어야 하므로 가장 마지막 계단에서부터 시작하는 것이 좋다.

 

맨 마지막 계단이 밟혀있다고 가정해보자.

그렇다면 그 전의 계단은 "마지막 - 1" 계단이거나, "마지막 - 2" 계단 일 것이다.

 

두 개의 경우에 문제 2번 조건을 적용시켜보자

 

1) 그전에 밟은 계단이 "마지막 - 1" 일 경우 반드시  "마지막 - 2" 계단을 밟으면 안 된다. - 연속된 3개의 계단을 밟아서는 안되므로

2) 그 전에 밟은 계단이 "마지막 - 2"일 경우 그 전 계단은 신경 쓰지 않는다. - 다이내믹프로그래밍을 적용시키면 되므로

내가 만약 다이나믹 프로그래밍을 통해 배열 "dp"에 앞에서부터 밟아온 계단 중 가장 최대의 값을 저장해 왔다면 다음 점화식을 세울 수 있다.

dp [i] = max(dp [i-2] + arr [i] , dp[i-3] + arr[i] + arr[i - 1])

import sys
input = sys.stdin.readline

n = int(input())
dp = []
arr = []
for _ in range(n):
    arr.append(int(input()))

if n == 1:
    dp.append(arr[0])
elif n == 2:
    dp.append(arr[0])
    dp.append(arr[0]+arr[1])
elif n == 3:
    dp.append(arr[0])
    dp.append(arr[0]+arr[1])    
    dp.append(max(arr[0]+arr[2],arr[1]+arr[2]))
else:
    dp.append(arr[0])
    dp.append(arr[0]+arr[1])    
    dp.append(max(arr[0]+arr[2],arr[1]+arr[2]))
    for i in range(3,n):
        dp.append(max(dp[i-3] + arr[i] + arr[i-1], dp[i-2] + arr[i]))

print(dp.pop())

 

여기서 조심해야 할 점은 만약 n에 1이나 2가 들어간다면 index에러가 날 수 있다.

따라서 n==1 일 경우와 n==2일 경우, n==3인 경우까지 if문을 통해 하드코딩으로 정해놓고

그다음에 for문을 통해 다이내믹 프로그래밍을 진행한다.