[Python Algorithm] 계단 오르기 BOJ #2579

문제

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

2579번: 계단 오르기

 

내 문제 풀이

import sys

n = int(sys.stdin.readline())
a = [0]*n # 현재 계단 밟고, 직전 계단 밟았다고 할 때
b = [0]*n # 현재 계단 밟고, 직전 계단 밟지 않았다고 할 때

for i in range(n):
    now = int(sys.stdin.readline())

    if i == 0:
        a[i] = now
        b[i] = now
    elif i == 1:
        a[i] = now + b[i-1]
        b[i] = now
    else:
        a[i] = now + b[i - 1]
        b[i] = now + max(a[i - 2], b[i - 2])

print(max(a[-1], b[-1]))

👉 DP 문제로, 현재 계단을 밟았을 때, 직전 계단을 밟았는지 안밟았는지 나눠 생각해주는게 포인트 !

• 계단을 한 칸씩 올라가면서 '현재' 계단을 밟았을 때의 경우의 수를 담을 a, b 리스트를 만들어주었다.
  a는 직전 계단을 밟았다고 가정하고, b는 직전 계단을 밟지 않았다고 가정하는 리스트이다.
• 주어진 조건에 따르면, 직전 계단을 밟았을 경우 전전 계단은 당연히 밟지 않았어야 한다.
  따라서 a 리스트에는 '현재' 계단의 값과 b의 직전 누적 값을 더해주었다.
• 직전 계단을 밟지 않았을 경우, 전전 계단은 당연히 밟았을 것이다.
  하지만 여기서 주의할 점은, 전전전 계단은 밟았을 수도 있고 안밟았을 수도 있다는 것이다.
  따라서 b 리스트의 경우 '현재' 계단 값에 전전에 누적된 a, b 값 중에 더 큰 값을 골라 더했다.

 

💡 피드백

• 위와 같은 유형의 DP 문제들은, 꼭 차례대로 반복하며 "'현재'것을 포함하면"을 전제로
  문제를 풀이하는 것을 기본으로 하면 좀 더 쉽게 접근하여 풀 수 있는 것 같다.