[백준 파이썬] 2579 계단 오르기

[백준 2579]

N = int(input())
stairs = [0] + [int(input()) for _ in range(N)] + [0, 0] # 인덱스 에러가 발생 안하도록 뒤에 0들을 추가했다. 
# 가장 앞의 0은 편의를 위해 추가

dp = [0] * (300+1) # 입력 범위까지
dp[1] = stairs[1]
dp[2] = stairs[1] + stairs[2]
dp[3] = max(stairs[2], stairs[1]) + stairs[3] # (1+3)번 째, (2+3)번 째 중 더 큰 값
for i in range(2, N+1):
	# 2번 전까지 최대 or 3번 전까지 최대 + 이전 계단 밟기
    dp[i] = max(dp[i-2], dp[i-3] + stairs[i-1]) + stairs[i]

print(dp[N])

계단을 건너는 방법으로부터 가능한 상태는

0. 일단 현재 칸은 밟은 상태
1. 이전 칸을 밟는다.
2. 이전 칸을 밟지 않고 그 전 칸을 밟았다.

2번 경우는 1칸 전을 밟지 않았기 때문에 2칸 전에 점수를 그대로 가져오면 된다. 2칸 전을 밟았으므로 그 다음 칸을 건너뛴다면 현재 칸 점수를 바로 더해주면 되기 때문

1번 경우는 현재 칸도 밟고 1칸 전도 밟았기 때문에 2칸 전은 밟지 않아야한다. 그래서 3칸 전을 밟아 얻은 점수를 가져오고 현재의 1칸 전 점수를 더해주면 된다.

이 두 경우를 비교해 더 큰 값을 가져오고 현재 칸의 점수를 더해주면 현재 칸의 최대 점수가 결정된다.