728x90
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
def solution(N, data_list):
# memo 와 자릿수 맞추기
data_list = [0] + data_list
# DP
# 2 까지는 미리 채우기
memo = [0 for _ in range(N+1)]
memo[1] = data_list[1]
# N 이 1이면
if N == 1:
return memo[1]
memo[2] = memo[1] + data_list[2]
# N 이 2면
if N == 2:
return memo[2]
for i in range(3, N+1):
# 점화식
memo[i] = max(memo[i-2], memo[i-3] + data_list[i-1]) + data_list[i]
return memo[-1]
N = int(input())
data_list = [int(input()) for _ in range(N)]
print(solution(N, data_list))
728x90
'Coding Test > BaekJoon_Python' 카테고리의 다른 글
| 백준 11726 <2Xn 타일링> Python (0) | 2023.10.31 |
|---|---|
| 백준 11659 <구간 합 구하기 4> Python (0) | 2023.10.31 |
| 백준 1149 <RGB 거리> Python (1) | 2023.10.30 |
| 백준 1463 <1로 만들기> Python (0) | 2023.10.29 |
| 백준 9095 <1, 2, 3 더하기> Python (1) | 2023.10.29 |