[백준/python] 2579번 : 계단 오르기

알고리즘 분류 DP

🔗 문제

📎 문제 출처 계단 오르기

---

🔗 코드

stairs = [0]*301
n=int(input())
for i in range(n):
  stairs[i]=int(input())

op=[0]*301
op[0]=stairs[0]
op[1]=stairs[0]+stairs[1]
op[2]=max(stairs[0]+stairs[2],stairs[1]+stairs[2])

for i in range(3,n):
  op[i]=max(op[i-3]+stairs[i-1]+stairs[i], op[i-2]+stairs[i])

print(op[n-1])

---

전형적인 점화식을 사용하는 Dynamic Programming 문제이다. 최종 값을 구하기 전까지 이전 값들을 점화하여 하나씩 풀어가는 방식이다.

코드에서 op는 인덱스의 계단까지 올라갔을 경우의 최댓값을 저장하는 배열이다.

op[0]은 그 자체로 최댓값이기 때문에 stairs[0]을 대입한다.

op[1]의 최댓값은 stairs[0]과 [1]의 합이다.

op[2]는 0을 거쳐 올라올 것인지, 1을 거쳐 올라올 것인지를 비교해 더 큰 값을 취한다. 0과 1 모두를 거치게 된다면 제약조건에 위배되기 때문이다.

이제부터가 중요하다.

n-1번째를 거치느냐,
n-2번째를 거치느냐 를 결정해야한다.

n-1번째를 거치게 된다면 op[i-3] + stairs[i-1] + stairs[i] ,
n-2번째를 거치게 된다면 op[i-2] + stairs[i] 가 된다.

이제 위의 점화식을 통해서 루프를 돌리며 n-1번째(실제 n번째 계단)의 최댓값을 찾아주면 된다.