Search

BOJ 2579 계단 오르기

태그
다이나믹 프로그래밍

문제 설명

•
마지막 계단을 반드시 밟는 조건하에, 연속된 세 개의 계단을 밟지 않으면서 한 번에 1칸 또는 2칸씩 올라갈 때 얻을 수 있는 최대 점수를 구하는 문제

예제 입력/출력

•
입력1
6 10 20 15 25 10 20
Plain Text
복사
•
출력1
75
Plain Text
복사

제약 조건

•
0<0 < 계단의 개수 ≤300≤ 300
•
0<0 < 각 계단의 점수 ≤10,000≤ 10,000

문제 풀이

접근 1 브루트 포스 (완전 탐색) - O(2n)O(2^n)
접근 2 그리디
•
접근 3 DP - O(N)O(N)
◦
브루트 포스 방식에서는 같은 계단에 대해 여러 번 동일한 연산을 수행하므로 중복 계산이 발생하여 비효율적이다.
◦
DP를 사용하면 한 번 계산한 값을 저장하여 재사용함으로써 중복 연산을 줄이고 최적해를 효율적으로 구할 수 있다.
◦
DP 테이블 정의
▪
dp[n]dp[n]: nn번째 계단까지 도달했을 때 얻을 수 있는 최대 점수
•
1≤n≤3001 ≤ n ≤ 300
◦
DP 관계식
▪
계단을 오르는 방법
1.
한 칸 전 계단(n-1)에서 오는 경우
•
단, n-2 → n-1 → n가 되면 연속 3칸을 밟게 되므로 n-3에서 n-1로 오고 n으로 이동해야 한다.
•
즉, dp[n-3] + arr[n-1] + arr[n]
2.
두 칸 전 계단(n-2)에서 오는 경우
•
dp[n-2] + arr[i]
▪
dp[i]=max(dp[n−2],dp[n−3]+arr[n−1])+arr[n]dp[i] = max(dp[n - 2], dp[n - 3] + arr[n - 1]) + arr[n]
◦
초기값 처리
▪
dp[1]=arr[1]dp[1] = arr[1]
▪
dp[2]=arr[1]+arr[2]dp[2] = arr[1] + arr[2]

풀이 코드

•
접근 3 DP - O(N)O(N)
# 입력 값 받기 N = int(input()) arr = [0] * (N + 1) for i in range(1, N + 1): arr[i] = int(input()) # 예외 처리 if N == 1: print(arr[1]) exit() # DP (Bottom-Up) dp = [0] * (N + 1) dp[1] = arr[1] dp[2] = arr[1] + arr[2] for n in range(3, N + 1): dp[n] = max(dp[n - 3] + arr[n - 1], dp[n - 2]) + arr[n] print(dp[N])
Python
복사