백준 알고리즘 2579번

이 문제는 각 단계마다 경우의 수가 몇가지 존재하고 그 중 가장 큰 값만을 저장하고 단계를 진행하는

다이나믹 프로그래밍문제이다. 하지만 몇가지 제약이 존재하는 DP라고 볼 수 있다.

조건을 회피하고 생각하는 것보다 조건을 처음부터 생각하며 DP 점화식을 세우는 것이 적절하다.

DP문제는 이 점화식을 세우는 것이 관건인데, 뒤에서부터 고려하여 식을 짜는 것이 수월하다.

제약 조건을 살펴보면

1. 한번에 1칸 또는 2칸을 오를 수 있다.

2. 연속 3칸을 밟은 순 없다.

3. 마지막 계단은 반드시 밟아야 한다.

뒤에서부터 생각하면, 마지막 계단은 반드시 밟아야하고 연속적으로 3칸은 밟을 수 없으므로

나올 수 있는 경우의 수는 2가지이다.

1. 전 단계의 계단을 밟는 경우

2. 전 단계의 계단을 밟지 않는 경우

즉, 위와 같은 경우의 수 2가지를 점화식으로 나타내면 다음과 같다.

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

위의 식을 적용하여 완성된 코드

n = int(input())

stair = []

for i in range(n):
    temp = int(input())
    stair.append(temp)

dp = []

dp.append(stair[0]) # 첫 번째
dp.append(stair[1] + dp[0]) # 두 번째
dp.append(max(stair[2] + stair[0], stair[2] + stair[1]))

for i in range(3, n):
    dp.append(max(stair[i] + dp[i - 2], stair[i] + stair[i - 1] + dp[i - 3]))

print(dp[n - 1])