[백준] 2579번(python 파이썬)

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

현재 계단으로 온 경우는 2가지이다.

1. 1단계전 계단에서 온경우

2. 2단계전 계단에서 온경우

 

1번일 경우

연속으로 계단을 올라갈 수 없으므로

이전에 2단계전 계단에서 올라온 경우에 현재 계단의 비용을 더한다.

 

2번일 경우

2단계전 계단에서 온경우의 최대값과 현재 계단의 비용을 더한다.

 

cost[0][0]. cost[0][1] 은 0단계 임으로 0이다

i, j	0 : 연속으로 계단을 1칸씩 올라온경우 ex) 1->2	1 : 2단계씩 계단을 오른 경우
1	cost[1]	cost[1]
2	dp[1][1] + cost[2]	max(dp[0][0], dp[0][1]) + cost[2]
3	dp[2][1] + cost[3]	max(dp[1][0], dp[1][1]) + cost[3]
4	dp[3][1] + cost[4]	max(dp[2][0], dp[2][1]) + cost[4]
5	dp[4][1] + cost[5]	max(dp[3][0], dp[3][1]) + cost[5]
6	dp[5][1] + cost[6]	max(dp[4][0], dp[4][1]) + cost[6]

 

n = int(input())
cost = [0]
dp = [[0] * 2 for _ in range(n + 1)]  # [][0] : 연속, [][1] : 2칸
for _ in range(1, n + 1):
    cost.append(int(input()))


def stair():
    dp[1][0] = cost[1]
    dp[1][1] = cost[1]
    for i in range(2, n + 1):
        for j in range(2):
            if j == 0:
                dp[i][j] = dp[i - 1][1] + cost[i]
            else:
                dp[i][j] = max(dp[i - 2]) + cost[i]


stair()
print(max(dp[n]))