728x90
반응형
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
Python
import sys
input = sys.stdin.readline
n = int(input().rstrip())
arr = [0]+[int(input().rstrip()) for _ in range(n)]
dp = [[arr[i], arr[i]] for i in range(n+1)]
for i in range(2, n+1):
dp[i][0] += dp[i-1][1] # 직전 계단은 건너 뛰어서 온 계단만 가능
dp[i][1] += max(dp[i-2]) # 두 칸 뒤의 계단은 어디서 오든 상관 없음
print(max(dp[-1]))728x90
반응형
'Algorithm Problems' 카테고리의 다른 글
| [백준][Python] 19538번 루머 - 그래프,BFS (0) | 2021.09.17 |
|---|---|
| [백준][Python] 11724번 연결 요소의 개수 - DP (0) | 2021.09.10 |
| [백준][Python] 11729번 하노이탑 이동 순서 - 재귀(하노이탑) (0) | 2021.08.31 |
| [백준][Python] 색종이 만들기 - 재귀(분할정복) (0) | 2021.08.31 |
| [백준][Python] 1932번 정수 삼각형 - DP (0) | 2021.08.30 |