[백준/파이썬] 2579번 계단 오르기 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 2579번 계단 오르기
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

계단 점수가 주어질 때 연속 3칸을 밟지 않는 조건으로 마지막 계단까지 얻을 수 있는 최대 점수를 구하는 문제입니다.

코드

n = int(input())

t = [0]+[int(input()) for _ in range(n)]
d = [0]
for i in range(1, n+1):
    d.append(max(t[i-1] + t[i] + (d[i-3] if i > 2 else 0),\
                 t[i] + (d[i-2] if i > 1 else 0)))

print(d[n])

설명

i번째 계단에서 (i-1, i) 연속 선택과 i 단독 선택의 경우를 비교해 DP로 최댓값을 누적합니다.

---

• 백준 문제풀이 전체 목록 보기

---