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

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

2579번: 계단 오르기

 

 

 

조건

• 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임

 

• 계단을 밟으면 해당 계단에 쓰여 있는 점수를 얻게 된다.
• 아래 규칙을 지켜서 얻을 수 있는 점수의 최댓값을 구하라
  • 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
  • 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
  • 마지막 도착 계단은 반드시 밟아야 한다.

 

접근 방법

• DP를 이용하여 계단 점수의 합을 기록해주며 진행하면 된다.
• 계단 수+1만큼의 DP테이블을 만들어준다.
• 연속된 계단을 못 밟기 때문에, DP의 연속 된 값을 더해주는 것이 아닌
  • 현재 계단의 값 + DP의 2번째 이전의 값
  • 현재 계단의 값 + 직전 계단의 값 + DP 3번째 이전의 값
  • 위 2개의 값 중 최댓값을 선택해준다.
• 위 그림의 사진을 예시로 들면
  • DP = [0,10, 0, 0, 0, 0, 0] 에서 시작
  • 2번째 계단의 값 = 20
  • 따라서 DP[2]는 20+0와, 20+10+0 중 최댓값인 30, DP = [0,10, 30, 0, 0, 0, 0]
  • 3번째 계단의 값 = 15
  • DP[3] => 15+10, 15+20+0 =35, DP = [0,10, 30, 35, 0, 0, 0]
  • 4번째 계단의 값 = 25
  • DP[4] = 25+30, 25+15+10 => 55, DP = [0,10, 30, 35, 55, 0, 0]
• 위와 같이 갱신해주며 나가면 된다.

 

 

import sys  
sys.stdin = open('input.txt')  
  
  
N = int(input())  
stair = [int(input()) for _ in range(N)]  
stair = [0] + stair  
DP = [0]*(N+1)  
DP[1] = stair[1]  
for i in range(2, N+1):  
    # 최댓값으로 갱신 - 현재 값 + 2계단전까지의 dp값, 현재 계단 + 직전 계단 + 3계단 전의 값  
    # 위 2개의 값은 3개의 계단을 연속으로 밟지 않는 선에서 최댓값을 구해주는 방식    
    DP[i] = max(stair[i] + DP[i-2], stair[i]+stair[i-1]+DP[i-3])  
  
print(DP[-1])