[Python] 백준 2579번 계단 오르기

문제

2579번: 계단 오르기

입력

• 입력의 첫째 줄에 계단의 개수가 주어진다.
• 둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

• 첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

입력 예제

6
10
20
15
25
10
20

출력 예제

75

문제 풀이

• 각 경우에서의 최댓값을 구해야 하므로 dp[0]의 값은 array[0]의 값을 그대로 대입한 값이다.
• 두 번째 계단에서의 최댓값은 첫번째 계단, 두번째 계단을 모두 밟은 경우 이므로, dp[1]의 값은 array[0] + array[1]
• 세 개의 계단을 연속해서 밟을 수 없으므로, 세 번째 계단에서의 최댓값은 첫 번째 계단과 두 번째 계단을 밟은 경우와 두 번째 계단과 세 번째 계단을 밟은 값 중 더 큰 수이다.
• 마지막 계단은 무조건 밟아야 하므로, 마지막 계단을 밟지 않는 dp[i - 1]의 값은 고려하지 않는다.
• 따라서 점화식은 아래와 같다.

dp[i] = max(dp[i - 2] + array[i], dp[i - 1] + array[i - 1] + array[i])

• 점화식을 통해 값을 채워나간 후, 마지막 계단에 들어있는 값을 출력하면, 계단을 올라 얻을 수 있는 최댓값을 구할 수 있다.

코드

n = int(input())
array = [0] * n
dp = [0] * 301
for i in range(n):
    array[i] = int(input())

dp[0] = array[0]
dp[1] = array[0] + array[1]
dp[2] = max(array[0] + array[2], array[1] + array[2])

# 마지막 계단 무조건 밟아야 하므로 밟지 않는 경우 고려X
for i in range(3, n):
    dp[i] = max(dp[i - 2] + array[i], dp[i - 3] + array[i - 1] + array[i])

# 최댓값 출력
print(dp[n - 1])