BOJ 2579 계단 오르기

https://www.acmicpc.net/problem/2579
시간 1초, 메모리 128MB
input :

• N (1 <= N <= 300)
• S (1 <= S <= 10,000)

output :

• 점수의 최댓값을 출력.

조건 :

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

2개의 변수를 이용해서 1. 2. 일 때를 구분 해주고.
그림에서는 y 자리가 0 일 때는 한 계단을 오르는 것. 자리가 1일 때는 두 계단을 오르는 것이다.

실패.

계단은 2개를 밟을 수 있는데 하나만 따져서 문제인가 싶어서.
0번(아직 2개를 밟을 수 있음)
1번(아직 1개를 밟을 수 있음)
2번(못 밟음)
으로 나눠서 했는데 틀렸다.

사람들 풀이를 보니 탑 다운 으로 풀었는데 맨 처음 접근하던게 그나마 맞긴 했다.

마지막 계단에 도착하는 경우.
1. 바로 직전 계단에서 올라옴.
2. 2계단 밑에서 올라옴.
이것인데.

• 바로 직전에서 올라오려면. 이미 1칸을 밟고 있어야 한다. 즉, i - 1번째 계단 값도 생각을 해야 하고. 그 전의 dp 값을 더 해 주어야 한다.
  i - 1 번째 계단을 올라올 때는 무조건 2계단 밑에서 올라오기 때문에 dp[(i - 1) - 2] 도 더해준다.
• 2계단 밑에서 올라오는 경우는 그냥 dp[i - 2]를 더해주자.

import sys

N = int(sys.stdin.readline())
data = [0 for i in range(301)]
dp = [0 for i in range(301)]

for i in range(N):
    S = int(sys.stdin.readline())
    data[i] = S
    
dp[0] = data[0]
dp[1] = data[1] + data[0]
dp[2] = max(data[1] + data[2], data[0] + data[2])

for i in range(3, N):
    dp[i] = max(data[i] + data[i - 1] + dp[i - 3], data[i] + dp[i - 2])

print(dp[N - 1])