[백준 2579번] 계단 오르기 문제 풀이

<문제>

 

 

 

 

<입출력>

 

 

 

 

<풀이>

 

1. 계단이 1, 2개 일때는 모두 더한 값이 최대 값이다.

2. 계단이 3개 이상일 때는 현재 계단을 k (k>=3)번 이라 할때, (price[k] + price[k-2])와 price[k] + price[k-1] + price[k-3]) 의 값을 비교하여 최댓값을 저장해주어야 한다.

 

 

 

 

 

 

<코드>

n = int(input())

s = [int(input()) for _ in range(n)] # 각 계단의 점수 리스트

max_score = [0] * (n)

if len(s) <= 2:                        # 계단이 1,2개일 때는 총합
    print(sum(s))

else:                                   # 계단이 3개 이상일 때
    max_score[0] = s[0]                 # 첫번째 계단
    max_score[1] = s[0] + s[1]          # 두번째 계단
    for i in range(2, n):               # 세번째 계단부터 비교해서 최대값 저장
        max_score[i] = max(max_score[i - 3] + s[i - 1] + s[i], max_score[i - 2] + s[i])

    print(max_score[n-1])

 

 

 

 

 

 

<결과>