Baekjoon / 계단오르기

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

2579번: 계단 오르기

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

https://serendipity-37.tistory.com/41

Baekjoon / DP / 포도주 시식

포도주 시식 문제와 동일한 형태의 문제이다.

Input 조건만 조금 달라서 변경해주었다.

 

Solution

n = int(input())
step = [0]
for _ in range(n):
    a = int(input())
    step.append(a)

def solution(n, step):
    dp = [False] * (n+1)
    dp[0] = 0
	
    # n은 300이하 자연수라는 조건이기에, 1 혹은 2가 나올 수도 있다.
    if n == 1 :
        return step[1]
    elif n == 2 :
        return step[1]+step[2]
    else :
        dp[1] = step[1]
        dp[2] = max(dp[1]+step[2], step[2])

        for i in range(3,n+1):
            a = dp[i-2]+step[i]	 # i-1 건너뛰고 i번째 포함한 경우
            b = dp[i-3]+step[i-1]+step[i]  # i-1,i번째 연속으로 포함한 경우, i-2는 건너뛰어야함
            # c = dp[i-1]  # 마지막 계단을 무조건 포함해야하니까 제외됨.
            dp[i] = max(a,b)
        return dp[-1]

print(solution(n,step))