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 |
블로그의 정보
농담곰담곰이의곰담농
브이담곰