[Python] 백준 2579 계단 오르기

1. 문제 링크

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

2579번: 계단 오르기

---

2. 문제 요약

계단에 점수가 있을 때 게임에서 얻을 수 있는 점수의 최댓값을 구한다. 단 3개 이상의 연속된 계단은 안됨!

 

---

3. 아이디어 정리

• dp[i][j] 정의: 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 최댓값. i 계단은 밟음
• 점화식 (연속으로 최대 2개만 가능하니 아래 두 점화식이 나온다.)
  • dp[i][1] = max(dp[i - 2][1], dp[i - 2][2]) + array[i] # 연속 1개만 밟아야한다(현재 계단만) 따라서 현재 -2 계단 중 최댓값을 더한다.
  • dp[i][2] = dp[i - 1][1] + array[i] # 연속 2개를 밟아야 한다. 따라서 이전 계단 밟은 값 중 최댓값을 더한다.

---

4. 문제 풀이

4-1. 내 풀이

import sys

n = int(sys.stdin.readline().split()[0])
array = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
    array[i] = (int(sys.stdin.readline()))

if n == 1:
    print(array[1])
else:
    # 초기 세팅 d[i][j] - 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을때 최댓값
    d = [[0, 0, 0] for _ in range(n + 1)]
    d[1][1] = array[1]
    d[1][2] = 0
    d[2][1] = array[2]
    d[2][2] = array[1] + array[2]

    for i in range(3, n + 1):
        # 현재까지 연속으로 1개만 밟은 경우는 현재 i - 2 d에서 값 얻기 
        d[i][1] = max(d[i - 2][1], d[i - 2][2]) + array[i]
        # 현재까지 연속으로 2개 밟은 경우는 i -1(이전에) 1개 밟은 최댓값 + 현재 계단 점수 
        d[i][2] = d[i - 1][1] + array[i]   # 전계단 밝고, 현재계단 밟음

    print(max(d[n][1], d[n][2]))

 

---

5. 결론

• 2차원 dp문제