[백준/Python] 2579번 계단 오르기 풀이

문제 설명

---

 

---

문제 풀이

---

dfs를 통해 하나 또는 두 계단을 밟으며 세 개의 계단을 연속해서 밟는 경우를 가지치면 어떨까? 라는 생각을 하였지만 생각보다 조건처리가 번거롭고 2³⁰⁰ 은 생각보다 너무 큰 숫자가 될 것 같아 포기하고 dp를 생각했다.

 

점화식을 세우려고 패턴을 찾다가 그냥 규칙을 이용하기로 했다.

1. 최대 2번 연속된 계단을 이용할 수 있으니 ONE,TWO를 통해 state로 구별해 연속된 계단을 몇칸 밟았는지 확인한다.
   (ONE에는 1칸 연속된 계단을 이용한 값, TWO에는 2칸 연속된 계단을 이용한 값)
2. ONE의 경우 2칸 이전 계단에서 값을 받아오고 TWO의 경우 바로 이전과 두칸 이전 계단 중 ONE state에 있는 값만 가져와 비교한다.
3. N까지 쌓아 N번째 계단에 도달한 경우의 최고 값을 출력한다.

 

---

코   드

---

import sys
N = int(sys.stdin.readline())
ONE = 0
TWO = 1

stair = [0]
save = [[0, 0] for i in range(N + 1)]

for i in range(N):
    stair.append(int(sys.stdin.readline()))

save[1][ONE] = stair[1]
save[1][TWO] = stair[1]

for i in range(2, N+1):
    save[i][TWO] = save[i-1][ONE] + stair[i];
    save[i][ONE] = max(save[i-2][ONE], save[i-2][TWO]) + stair[i];

print(max(save[N]))

---

느낀점: 실버라고 하지만 다이나믹 프로그래밍 자체가 난이도와 무관하게 점화식 세우기가 어려운 문제같다.

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

2579번: 계단 오르기