Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 2579 계단 오르기
백준 2579 계단오르기
문제
계단 아래 시작점부터 계단 꼭대기 도착점까지 가는 게임이 있다.
각각의 계단에는 일정한 점수가 쓰여져 있으며 해당 계단을 밟으면 쓰여져 있는 점수대로 점수를 얻게 된다.
계단을 오르는 데는 규칙이 있다.
- 한 번에 한계단 또는 두 계단씩만 오를 수 있다.
- 연속된 세 개의 계단을 밟을 수 없다. (시작점은 이 규칙에 포함되지 않는다.)
- 마지막 도착 계단은 반드시 밟아야 한다.
총 점수의 최댓값을 구하는 프로그램을 작성하시오.
입력
- 첫째줄: 계단의 개수 n
- 두번재줄 ~: 각 계단의 점수
출력
총점의 최댓값
해결 방식
다이나믹 프로그래밍 방식으로 풀었다.
- i번째 계단과 i-1번째 계단을 연속으로 밟는 경우
- i-3번째 계단을 밟고 올라왔어야 한다.
- i번째 계단과 i-2번째 계단을 밟는 경우
- 무슨 계단을 밟고 올라와도 상관 없다.
예를 들어 10, 20, 15, 25, 10, 20 순으로 점수가 매겨져 있다 가정하자!
- dp[0] = 10, dp[1] = 10 + 20 = 30
- dp = [10, 30]
- dp[2]에는 3번째 계단을 밟는 경우
- 1번째 계단을 밟는 경우: 10 + 15 = 25
- 2번째 계단을 밟는 경우: 20 + 15 = 35
- 35 저장
- dp = [10, 30, 35]
- dp[3]: 4번째 계단을 밟는 경우
- 2번째 계단을 밟은 경우: dp[2] + (현재 점수) = 35(2번째 계단까지 점수의 최대 합) + 20 = 55
- 3번째 계단을 밟는 경우: dp[1] + (현재 점수) = 10(1번째 계단까지 점수의 최대 합) + 15(이전 계단) + 25(현재 계단) = 50
- 55 저장
- dp = [10, 30, 35, 55]
- 이와 같은 과정을 계속 반복한다.
코드
import sys
input = sys.stdin.readline
n = int(input())
stairs = []
dp = [0] * (n)
for _ in range(n):
stairs.append(int(input()))
if n == 1:
dp[-1] = stairs[0]
elif n == 2:
dp[-1] = sum(stairs[:2])
else:
dp[0] = stairs[0]
dp[1] = stairs[0] + stairs[1]
for i in range(2, n):
print(dp[i-2]+stairs[i], dp[i-3]+stairs[i-1]+stairs[i])
dp[i] = max(dp[i-2]+stairs[i], dp[i-3]+stairs[i-1]+stairs[i])
print(dp)
print(dp[-1])
