📎 문제 출처
https://www.acmicpc.net/problem/2579
📌 문제 설명
❓ 풀이 방법
이 전 계단까지의 점수의 합의 최댓값을 사용하기 때문에 다이나믹 프로그래밍을 사용했다.
연속된 3개의 계단을 밟을 수 없다는 조건이 없었다면 dp[i] = Math.max(dp[i-1] + dp[i-2]) + stair[i]와 같은 점화식으로 간단하게 해결할 수 있었겠지만 해당 조건 때문에 시간이 조금 걸렸다.
계단을 오르는 방법이 1+1+1은 안되기 때문에 2+1 또는 1+2 중 하나이다.
즉, n 번째 계단까지 갈 수 있는 최대 점수는
(n-3 번째 계단까지 갈 수 있는 최대 점수 + n-1 번째 계단의 점수) 와
(n-1 번째 계단까지 갈 수 있는 최대 점수) 중 더 큰 값에 n 번째 계단의 점수를 더한 값이다.
이 때, n이 1일 경우 dp[2]의 값은 초기화할 필요 없기 때문에 예외 처리해 주도록 주의해야 한다.
📌 Code
