[BOJ/Python] 2579 : 계단 오르기

👉 문제 링크

👉 전체 코드

n = int(input())

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

if n==1:
    print(dp[1])
else:
    score = [0] * (n+1)
    score[1] = dp[1]
    score[2] = dp[1] + dp[2]
    for i in range(3,n+1):
        score[i] = max(dp[i]+dp[i-1]+score[i-3], dp[i]+score[i-2])
    
    print(score[n])

👉 풀이

첫번째 경우 : 마지막-1 계단일 경우 마지막-2 계단은 밟으면 안된다.
두번째 경우 : 마지막-2 계단일 경우 전 계단은 신경쓰지 않아도 된다.

앞에서부터 최댓값을 저장할 배열이 필요 -> 코드의 score

따라서,
i번째 계단의 최댓값은 현재 계단 + i-1 번째의 점수 + i-3번째까지의 최댓값
현재 계단 + i-2번째까지의 최댓값 중 큰 값이다.

dp = [0] 을 해준 이유는 배열의 0번째에 0을 삽입하기 위함이다.