계단 오르는 데는 다음과 같은 규칙이 있다.
1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.
# 1
import sys
input = sys.stdin.readline
N = int(input())
arr = [0]
for _ in range(N):
arr.append(int(input()))
if N < 3: # 계단개수 2개 이하
print(sum(arr))
exit(0)
dp = [0] * (N + 1) # 현재 계단의 최댓값
# 1~3 초기값
dp[1] = arr[1]
dp[2] = arr[1]+arr[2]
dp[3] = max(arr[1],arr[2])+arr[3]
for i in range(4, N+1):
dp[i] = max(arr[i-1]+dp[i-3], dp[i-2]) + arr[i]
print(dp[N])
# 2
import sys
input = sys.stdin.readline
N = int(input())
arr = [0]
for _ in range(N):
arr.append(int(input()))
if N < 3: # 계단개수 2개 이하
print(sum(arr))
exit(0)
dp = [0] * (N+1) # 밟지 않을 계단 점수의 최솟값
for i in range(1,4): # index: 1,2,3 초기값 설정
dp[i]=arr[i]
for i in range(4, N):
dp[i] = min(dp[i-2], dp[i-3]) + arr[i]
print(sum(arr)-min(dp[N-1], dp[N-2]))
위: 1번 방법
아래: 2번 방법