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

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

2579번: 계단 오르기

 

코드

n = int(input())
st = [0] * 301      # n+1 말고
for i in range(1, n + 1):
    st[i] = int(input())

dp = [0] * 301      # n+1 말고 (n이 하드 코딩하는 인덱스를 커버하지 않는 작은 수로 들어올 수 있음)
dp[1] = st[1]
dp[2] = st[1] + st[2]
dp[3] = max(st[1] + st[3], st[2] + st[3])

for i in range(4, n + 1):
    dp[i] = max(dp[i - 3] + st[i - 1] + st[i], dp[i - 2] + st[i])

print(dp[n])

 

계단 3개를 연달아 밟을 수 없기 때문에

구하려는 계단의 직전과 2번째 전 계단이 아닌

3번째 전과 2번째 전이 기준이 되어야 한다.

 

마지막 계단은 무조건 밟힌 계단이기 때문에

1. 직전 계단을 밟고 올라왔다면, 2번째 전 계단은 밟지 않았어야 하고

2. 2번째 전 계단을 밟고 +2 해서 올라왔다면, 3번째 전의 값에 2번째 전 계단의 점수 값과 마지막 계단 점수 값을 더해주고

그 두 값 중에서 최대 값을 구해주면 된다.

 

마지막 계단을 밟았다는 것을 기준으로

규칙을 만족하기 위해서는 이전 값들을 어떻게 활용할 수 있을지를

초점으로 두고 생각하면 좋았겠다.

 

구하려는 DP값을 기준으로 이전 값들을 활용하는 방식으로

역으로 생각하는 연습을 충분히 해야 할 것 같다