[BOJ/Step15] 2579 : 계단 오르기 (Python)

www.acmicpc.net/problem/2579

2579번: 계단 오르기

---

앞에 문제들이랑 비슷했는데 이건 조금 헤맸다..

다른 사람들이랑 같은 로직의 코드인데 계속 인덱스 에러가 나서 대체 왜그러나 했는데

stair랑 cost를 n까지만 저장해서 그랬다
n이 1인 경우랑 2인 경우에 리스트 인덱스 너머로 접근하니까 계속 오류가 난 것 ㅜ

이번에도 멍청했다...

 

1. 각 계단의 점수를 stair 리스트에 저장하고 각 계단에 도달할 점수의 최댓값을 저장할 cost리스트를 생성, 0으로 초기화

2. cost[0]에 stair[0]을 저장 ( 첫번째 계단은 이전 계단이 없기 때문에 어떻게 올라가도 점수가 그대로 )

3. stair과 cost를 n 크기만큼만 만들었기 때문에 n이 1보다 큰지 확인하여 cost[1]에 stair[0] + stair[1]을 저장

    => n이 1이면 계단이 하나이기 때문에 stair[0]까지밖에 점수가 저장되어있지 않다

4. n이 2보다 큰지 확인하여 cost[2]에 stair[2] + (stair[0], stair[1] 중 더 큰 값)을 저장

    => stair[2]에 가는 방법은 stair[0]을 밟고 넘어가는 방법과, stair[1]을 밟고 넘어가는 방법 두가지가 있다

5. for문으로 cost[3]부터 cost[n-1]까지 점수를 계산한다

  5-1. cost[n] 에 가는 방법은 두가지이다

  5-2. stair[n-1] + stair[n-3] 을 밟는 방법.

          => 세 계단을 연속으로 밟아서는 안되기 때문에 바로 전 계단을 밟았다면 무조건 그 전전 계단을 밟아야만 한다

  5-3.  stair[n-2] 을 밟는 방법. 두 칸 전의 계단을 밟을 수 있다.

  => 세 칸 전의 계단까지 오는 최종 점수 + 한 칸 전의 계단 단독 점수 와 두칸 전의 계단까지 오는 최종 점수를 비교하여 더 큰 값을 stair[n]에 더해준다

  => stair[i] + max(stair[i-1] + cost[i-3], cost[i-2])

 

# 2579.py

n = int(input())

stair = [int(input()) for _ in range(n)]
cost = [0 for _ in range(n)]

cost[0] = stair[0]

if n > 1:
    cost[1] = stair[1] + stair[0]
if n > 2:
    cost[2] = stair[2] + max(stair[0], stair[1])

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

print(cost[n-1])