[파이썬] 백준 2579 : 계단 오르기

[파이썬] 백준 2579 : 계단 오르기

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

2579번: 계단 오르기

실버 3

DP

---

접근

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

계단을 한 계단 밟을지, 두 계단을 밟을지를 선택할 수 있다.

 

dp문제를 풀 때 개인적으로 가장 어려운 부분은, 메모이제이션을 문제에 따라 어떻게 활용해야할지를 잘 모르겠다는 것이다.

 

해당문제는 각 계단을 밟고 있을 때의 최댓값을 dp에 메모이제이션 해주어야 했다.

 

 

첫번째 계단을 밟는 최댓값은 10점

두번째 계단은 첫번째와 두번째 계단을 모두 밟아야하므로 10 + 20 = 30점이다.

 

세번째 계단은 세번째 계단의 점수와, 첫 번째 계단과 두 번째 계단의 점수 중에 큰 것과의 합이 된다.

따라서 15 + 20 = 35점이다.

 

각 계단에서의 최댓값을 dp라는 리스트에 할당해준다.

 

4번째~마지막까지 계단의 최댓값은 다르게 접근해야 한다.

이 범위에서의 계단을 i번째의 계단이라고 할 때,

i 번째 계단까지의 최댓값은

 

1.  i-2번째에서 2칸을 올라오는 경우
2.  i-3번째에서 i-1칸으로 2칸을 뛰어넘고 i칸으로 올라오는 경우

 

둘 중의 큰 값으로 선택해야 한다.

 

코드

import sys
n = int(sys.stdin.readline())
stair = [0] * 301
for i in range(1, n+1):
    stair[i] = int(sys.stdin.readline().rstrip())
dp = [0] * 301

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

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

print(dp[n])

 

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

 

stair리스트는 계단마다 부여된 점수이다.

dp는 각 계단까지의 최댓값을 할당한 리스트이다.

dp[i-3]까지의 최댓값에 두 칸을 건너 뛴 계단의 점수와 최종적으로 위치할 계단의 점수의 합과

dp[i-2]까지의 최댓값에 두 칸을 건너 뛰고 최종적으로 위치할 계단의 점수의 합 중에 최댓값을 고른다.