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

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

2579번: 계단 오르기

 

 

1. 코드 설명

n=int(input())

stairs=[0]*(n+3)

for i in range(n):

  stairs[i]=int(input())

dp = [0]*(n+3)

dp[0]=stairs[0]

dp[1]=stairs[0]+stairs[1]

dp[2]=max(stairs[2]+stairs[0], stairs[2]+stairs[1])

 

for i in range( 3, n) :

  dp[i] = max(stairs[i]+dp[i-2], stairs[i]+stairs[i-1]+dp[i-3])

  #print('max :' ,stairs[i]+dp[i-2],',', stairs[i]+stairs[i-1]+dp[i-3])

  #print ('dp :' , dp)

  #print('*'*50)

print(dp[n-1])

 

 

 

 

 

dp [ i ] 의 계산 방법은 두가지 경우로 나눌 수 있다.

 

(dp [ i ] = i번째 계단 밟았을때 총 합산 점수)

 

 

1. i번째 계단의 전 계단을 밟은 경우 : 

stairs[i]+stairs[i-1]+dp[i-3]

 

stairs[i] = 마지막 계단 점수

stairs[i-1] = 마지막 전 계단 점수

dp[i-2] = 이전까지의 점수 합산

 

2. i번째 계단의 전 계단을 밟지 않은 경우 (전 전 계단은 밟은 경우) : 

stairs[i]+dp[i-2]

stairs[i] = 마지막 계단 점수

dp[i-2] = 이전까지의 점수 합산

 

 

 

이 중 더 큰 값 (max) 이 dp[ i ]  가 된다.

 

 

 

 

 

2. 주의 사항

 

stairs = [int(input()) for _ in range(n)]

 

dp = [0]*(n)

 

이렇게 stairs 지정하게 되면 다음과 같은 부분에서 오류가 발생한다

 

 

n = 1 일땐 dp[1], stairs[1] 이 존재 x

dp[1] = stairs[0] + stairs[1]

 

 

n = 2 일땐 dp[2], stairs[2] 이 존재 x

dp[2] = max(stairs[0]+stairs[2], stairs[1]+stairs[2])

 

 

따라서 stairs 는 dp 와 마찬가지로 0 행렬을 먼저 만들고 인덱스 순으로 채워가는 방식으로 생성해야하며

 

범위는 n이 아니라 n+3 로 설정한다.