[#2579] 계단 오르기

문제

#2579 계단 오르기
Silver3
적용 알고리즘: 다이나믹 프로그래밍

---

풀이 방법

• 계단의 끝을 기준으로 도착 할 수 있는 방법을 생각하여 점화식을 세운다.
• i번째 칸에 도착할 수 있는 방법은 두가지이다.
  • 이전 칸(i-1)을 밟기(이 경우 총 점수는 i-3 번째 칸까지의 점수의 합 + i-1 칸의 점수 + i칸의 점수)
  • 전전칸(i-2)을 밟기(이 경우 전전칸까지의 점수의 합 + i칸의 점수)
• 점화식은 다음과 같다.
  • dp[i] = dp[i-3] + stair[i-1] + stair[i]
  • dp[i] = dp[i-2] + stair[i]
• 이를 합치면 다음과 같다.
  • dp[i] = max(dp[i] = dp[i-3] + stair[i-1] + stair[i], dp[i] = dp[i-2] + stair[i])

코드 흐름

1. 1, 2, 3칸의 경우 경우를 고려하여 나올 수 있는 가장 큰 값을 설정한다.
2. 점화식은 4번째 칸부터 진행된다. 1, 2, 3칸이 입력된 경우 별도로 답을 출력하고 종료 처리를 한다.
3. 4번째 계단부터 n번째 계단까지 점화식을 이용하여 큰 값을 저장해나간다.
4. 가장 마지막 칸의 점수를 출력한다.

코드

n = int(input())
stair = [int(input()) for i in range(n)]
stair.insert(0, 0)

if n <= 3:
    if n == 1:
        print(stair[1])
    if n == 2:
        print(stair[1] + stair[2])
    if n == 3:
        print(max(stair[1] + stair[3], stair[2] + stair[3]))
    exit()

dp = [0] * (n + 1)
dp[1] = stair[1]
dp[2] = max(stair[1] + stair[2], stair[2])
dp[3] = max(stair[1] + stair[3], stair[2] + stair[3])

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

print(dp[-1])

체감 난이도: 4.3/5
dp… 어느정도 풀 수 있겠다고 생각했는데 아직 한참 멀었다. 문제 형식만 조금 바뀌니까 또 어렵네… 더풀자. 아니 내가 이건 어떻게 처리하지? 싶은 부분의 처리가 이렇게 간단하다는게… 공부가 더 필요한 것 같다.