[baekjoon] 백준 2579번 : 계단 오르기 (by python)

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

2579번: 계단 오르기

 

정답 code

#계단오르기
import sys
input = sys.stdin.readline

n = int(input())
score = [0 for i in range(301)]
dp = [0 for i in range(301)]

for i in range(n):
    score[i] = int(input())

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

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

print(dp[n-1])

 

조건 정리

 

1. 계단은 한칸이나 두칸씩만 오를 수있다.

2. 시작지점 제외하고 연속된 세개의 계단은 밟을 수 없다.

3. 마지막 계단은 꼭 밟아야 된다.

 

 

solution

우선 계단의 스코어를 입력하기위한 score 리스트와

해당 계단까지 오기까지의 최대 점수를 저장할 dp리스트를 만든다 

*계단은 최대 300계단

 

조건에 맞게 계단을 오르기위해서 우선 맨마지막 계단을 밟는것에 주목해야된다.

맨마지막 계단을 밟기 위해서는 두가지 방법이 있는데

case1: end -1 계단을 밟고 한칸 오르는 경우(전계단이 end-3 이여야함)

case2: end -2 계단을 밟고 두칸 오르는 경우

 

case1의 경우에는 end-1계단 전 계단이 end-2계단이 되게 되면 (end-2, end -1, end)계단  이렇게 연속된 세계의 계단을 밟기 때문에 조건2번에 부합하지 않는다

따라서 case1의 경우에는 end-1계전 이전에는 end-3계단이여야 한다. 

case2의 경우에는 두칸을 올라 마지막에 도달하기 때문에 상관하지 않아도 된다.

 

이에 따라 나오는 식이 아래와 같다.

# case1  score[i]+score[i-1]+dp[i-3]
# case2  score[i]+dp[i-2]

dp[3] 이후에 도착하는 계단은 마지막 계단과 같이 밟아야 하는 계단임으로 위의 케이스 두개중에 max값을 저장하면 해당 계단 까지의 최대 스코어 값이 된다.