백준 2579. 계단 오르기

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

2579번: 계단 오르기

이런 문제에서 절실히 느끼는 것.. 조그만 문제부터 해결하고 이를 이용해서 답을 도출하자

 

3개의 계단이 있다고 할 때 구해보면, 1->3 혹은 2->3이 문제의 해결책이 된다. 이 중에서 가장 큰 값을 구하면 됨.

4개의 계단이 있다고 하면, 두 가지 경우의 수로 나뉜다. 3을 밟고 4를 밟거나, 2를 밟고 4를 밟거나.

따라서 계단이 1, 2, ... 일 경우 최댓값을 구하고, 3을 밟았을 때 최댓값 + 4 계단 값과 2를 밟고 4를 밟았을 때 값을 비교해서 더 큰 것을 넣어주면 된다.

 

n = int(input())
s = [0 for _ in range(301)]
dp = [0 for _ in range(301)]

for i in range(n):
	s[i] = int(input())
dp[0] = s[0]
dp[1] = s[0] + s[1]
dp[2] = max(s[0] + s[2], s[1] + s[2])

for i in range(3, n):
	dp[i] = max(dp[i-3] + s[i-1] + s[i], dp[i-2] + s[i])
print(dp[n-1])