[Baekjoon] 2579번 : 계단 오르기

실버 3

2579번: 계단 오르기

 

 

문제 풀이

계단이 3개 보다 작으면 모든 계단을 밟는 것이 무조건 최대이다. 

하지만 3개 이상일 경우엔 연속으로 세 개의 계단을 밟을 수 없기 때문에 두 가지 경우로 나누어 생각을 해볼 수 있다.

 

1) 한 칸 이전(n-1)에서 n번째 칸으로 온 경우

연속 두 개의 계단을 밟은 셈이므로 n-2칸은 밟을 수 없다.

따라서 n-3까지의 최대 점수에 한 칸 이전 계단의 비용과 현재 계단의 점수를 더한다.

2) 두 칸 이전(n-2)에서 n번째 칸으로 온 경우

연속이 되지 않기 때문에 그냥 n-2까지의 최대 점수에 현재 계단 점수를 더한다.

 

이 두개의 경우 중 큰 값이 n 번째 계단까지의 최대 점수가 된다.

 

코드

n = int(input())
stair = []
for _ in range(n):
    stair.append(int(input()))

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

for i in range(3, n+1):
    a = cost[i - 3] + stair[i - 2] + stair[i - 1] # 한 칸 이 전에서 온 경우
    b = cost[i - 2] + stair[i - 1] # 두 칸 이 전에서 온 경우
    cost[i] = max(a, b)

print(cost[n])