농담곰담곰이의곰담농

2579 계단 오르기

by 브이담곰

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

✔ 유형 : DP

✔ 문제 풀이: 계단을 오를 때, 앞에서부터 계산해서 최대값을 구하는 것이 아닌, 최종 도착지를 정해놓고 그전 계단을 밟았을때 밟지 않았을 때 중의 최댓값을 구해나가 memorization을 한다.

 

 

⬇️ 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list()
for _ in range(N):
    arr.append(int(input()))
DP = [0] * (N+1)


DP[1] = arr[0]
if N >=2:
    DP[2] = DP[1] + arr[1]

for i in range(3, N+1):
    DP[i] = max(DP[i-2] + arr[i-1], DP[i-3]+ arr[i-1]+ arr[i-2])
    
print(DP[N])

'Coding Test > Baekjoon' 카테고리의 다른 글

1932 정수 삼각형  (0) 2024.08.05
9461. 파도반 수열  (0) 2024.07.31
1700. 멀티탭 스케줄링  (0) 2024.07.25
3055. 탈출  (0) 2024.07.18
2665. 미로 만들기  (0) 2024.07.18

블로그의 정보

농담곰담곰이의곰담농

브이담곰

활동하기