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

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

2579번: 계단 오르기

프로그래머스 도둑질문제에서 막혀서 비슷한 유형이라고 소개된 계단오르기를 풀었다.

예전에 풀었던 문제라 금방 풀었음

 

문제 요약 : 계단 시작점부터 꼭대기 도착점까지 오를 때에 가장 높은 점수로 오르는 경우의 점수를 출력하라. 단, 계단은 연속해서 3계단을 갈 수 없으며 한번에 한계단씩 혹은 두계단씩 오를 수 있다.

 

풀이 ) 

DP문제

dp 리스트에는 그 계단을 밟을 때에 가장 높은 점수를 저장해준다.

연속해서 세개를 밟을 수 없다는 것 때문에 생각을 좀 해야하는 문제이다.

 

계단은 연속해서 세개를 밟을 수 없기 때문에, 무조건 첫번째 혹은 두번째임을 알 수 있다.

첫번째일 경우는 dp[i] = stair[i] + dp[i-2]가 된다.

두번째일 경우는 dp[i] = stair[i] + stair[i-1] + dp[i-3]이 된다.

import sys
input = sys.stdin.readline

N = int(input())
stair = [0]
dp = [0]*(N+1)

for i in range(1,N+1):
    stair.append(int(input()))
    if i == 1 :
        dp[1] = stair[1]
    elif i == 2 :
        dp[2] = stair[1] + stair[2]
    else :
        dp[i] = max(stair[i]+stair[i-1]+dp[i-3], stair[i]+dp[i-2])

print(dp[N])

DP문제는 생각하고 나면 쉽지만, 생각해내기까지가 쉽지 않다😂