계단오르기

🗂️ 문제링크: https://www.acmicpc.net/problem/2579  💡 접근법i번째 계단까지 오르는 데 최댓값을 구해야한다는 DP 관점은 이해했으나, 점화식을 제대로 세우지 못했다. 계단에 오를 수 있는 경우는 1. i-1번째 계단에서 오르는 경우, 2. i-2번째 계단에서 오르는 경우이다.하지만 i-1번째 계단에서 오르는 경우가 연속된다면, 최종적으로는 i-2 → i-1 → i번째 순으로 계단에 오르게 된다.이를 처리하기 위해 i-1번째 계단에서 오르는 경우에 대해서는 무조건 그 이전에는 i-3번째 계단을 거쳐야 한다. 따라서 이를 고려한 최종적인 점화식은 다음과 같다.dp[i] = max(dp[i-3] + stairs[i-1], dp[i-2]) + stairs[1] (i ≥ 2) ..

🗂️ 문제 링크: https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 💡 접근법 계단을 어떻게 올라갈까?가 아니라 계단을 어떻게 올라왔을까? 라는 관점에서 접근해야 한다. n번째 계단에 올라오기 위해서는 두 가지 경우가 있다. n-1번째 계단으로 오는 경우와 n-2번째 계단으로 오는 경우이다. n-1번째 계단으로 오는 경우에는 dp[n] = dp[n-3] + stairs[n-1] + stairs[n] 이다. n-2번째 계단으로 오는 경우에는 dp[n] = dp..