#28 [파이썬] 백준 2579번: 계단 오르기

<문제>

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

2579번: 계단 오르기

---

 

<소스코드>

1. Index Error가 난 코드 (실패)

import sys
input = sys.stdin.readline

score = []

n = int(input())
for _ in range(n):
    score.append(int(input()))

result = [0]*n
result[0] = score[0]
result[1] = score[0] + score[1]
result[2] = max(score[0] + score[2], score[1] + score[2])

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

print(result[-1])

 

위 코드는 n = 1 또는 n = 2일 때 score[2]와 같은 값이 없는 인덱스를 호출한다. 따라서 아래 코드에서는 n = 1인 경우와 n = 2이상인 경우를 따로 처리할 것이다. n = 3이상의 경우부터는 메인 수식으로 처리하는데, 계단의 인덱스를 0부터 시작했다면 n = 3일경우, 메인 수식으로 처리할 때 마이너스 인덱스로 넘어가버려서 인덱스 에러가 발생한다. 따라서 계단의 인덱스를 1부터 시작하고 점수가 없는 시작 단계를 0으로 처리하여 score 및 result 리스트에 포함한다. 

 

 

2. 수정한 코드 (통과)

import sys
input = sys.stdin.readline

score = [0]

n = int(input())
for _ in range(n):
    score.append(int(input()))

if n == 1:
    print(score[1])

else:
    result = [0]*(n+1)
    result[1] = score[1]
    result[2] = score[1] + score[2]

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

    print(result[-1])

---

 

<NOTE>

1. 재귀로 돌렸을 경우 시간초과 발생한다.

2. 계단을 올라갈 때 몇 번째 계단을 밟고 올라갈 지를 생각하기 보다는, 이미 계단을 올라와있다고 생각했을 때 어떤 계단을 밟고 올라왔는 지를 역으로 생각해본다. (knapsack문제와 유사하게 한 스텝씩 최대가치를 생각하면서 확장해나간다.)

2. 수식이 모든 경우를 포함하는 지 체크한다. (ex. n=1 등)