---

풀이

DP 배열과 입력을 받을 arr 배열을 선언 후 진행

1. dp[1] 은 1계단의 값
2. dp[2] 는 1 + 2 계단의 값
3. dp[3] 은 max(1 + 3, 2 + 3) 의 값이다.

계단이 쭉 있을때 최댓값은

1. 도착 2칸 앞 계단의 dp값 + 도착 계단
2. 도착 3칸 앞 계단의 dp값 + 도착 1칸앞 계단 + 도착 계단

의 두가지로 추려진다.

이유로는 한번에 1~2칸의 계단을 오를 수 있고, 3칸의 계단을 연속해서 밟을 수 없기 때문

1번의 경우는 한칸을 dp값과 현재 계단사이에 한칸 띄웠기 때문에 연속해서 밟는 경우는 생각하지 않아도 된다. 즉 최댓값에서 현재 계단을 더하면 됨.

2번의 경우는 조금 생각을 해야되는데
최종 도착지의 1칸 앞 계단의 dp는 알아도 의미가 없다. 최종 도착칸을 밟았을 때 3칸 연속 밟게되는 경우일 수 있기 때문
그렇기에 1칸 앞 계단을 밟으면서 최종칸을 밟으려면 2칸 앞은 건너 띄고 3칸앞의 최댓값을 구해서 1칸앞 계단값과 도착 계단 값을 더해주게 된다.

---

코드

#include <bits/stdc++.h>

using namespace std;

int n;
int stair[301];
int dp[301];

int main()
{
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> stair[i];
	}

	dp[1] = stair[1];
	dp[2] = stair[1] + stair[2];
	dp[3] = max(stair[1] + stair[3], stair[2] + stair[3]);

	for (int i = 4; i <= n; i++)
	{
		dp[i] = max(dp[i - 2] + stair[i], dp[i - 3] + stair[i - 1] + stair[i]);
	}

	cout << dp[n];

	return 0;
}

---

후기

---

도착 칸의 1칸 앞만 보면서 계속 상관관계를 따지려고 드니 전혀 성립이 안되서 지체가 됐지만

그래도 어찌저찌 풀었다.

지금까지 풀었던 DP문제 와는 다른, 발상의 전환이 필요한 문제였다고 생각한다.