[백준] 2579번 계단 오르기 : 파이썬(python) 설명

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

2579번: 계단 오르기

 

Hint

 

dynamic programming을 이용

 

계단을 밟을 경우를 두 가지로 나누어서 생각하자.

(i번째 계단을 밟을 경우 i-1번째를 밟고 오는 경우와

i-2번째를 밟고 오는 경우로 나누자)

 

 

Solution

T=int(input())
L=[]
for i in range(T):
    L.append(int(input()))
if T==1:
    print(L[0])
else:
    L[0]=[L[0],L[0]]
    L[1]=[L[0][0]+L[1],L[1]]

    for i in range(2, T):
        L[i]=[L[i]+L[i-1][1], L[i]+max(L[i-2])]

    print(max(L[T-1]))

T=계단 개수

L=계단 리스트

 

12번 line을 보면

L[i]를 특이하게 설정한 것을 볼 수 있습니다.

L[i]+L[i-1][1]은 기존 i번째 계단의 값과 그 전 i-1번째 계단의 값을

더한 것으로 볼 수 있는데

i-1번째 계단의 값은 그 동안 밟아온 계단의 값이 이미 더해져 있습니다.

 

즉, i-1번째에 30, 20, 25라는 계단을 밟고 왔으면

i-1번째 계단의 값은 L[i-1][1]=75가 되어있을 겁니다.

 

두 번째로는 L[i]+max(L[i-2])입니다.

해당 코드는 계단을 건너 뛰어서 밟은 경우입니다.

즉, i-2번째 계단을 밟고 i번째 계단을 밟을 때는

i-2번째 계단을 밟았을 동안의 결과 중 가장 큰 값을 가져오면 됩니다.

(i-2번째까지 하나밟고 한 번 뛰고 등등 모든 과정 무시)

 

for 구문을 돌리고 나면 L[i]=[i-1번째 계단을 밟은 값, i-2번째 계단을 밟은 값]으로

설정됩니다