https://www.acmicpc.net/problem/2579
이 문제는 i번째 계단에서의 점수가 i-1번째 계단을 밟는지 여부에 영향을 받으므로 DP를 이용해서 풀었다.
dp[i][j] 라는 배열에 아래 상황일 때의 최대 점수를 저장한다.
j=0일 때, i-1번째 계단을 밟지 않고 i번째 계단을 밟았으므로 i-2번째 계단을 밟은 것이다.
j=1일 때, i-1번째 계단을 밟고 i번째 계단을 밟았으므로 i-2번째 계단을 밟지 않은 것이다.
따라서 총 점수의 최댓값은 max(dp[n][0], dp[n][1])이다.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> step(n+1, 0);
vector<vector<int>> dp(n+1, vector<int> (2, 0));
for(int i=1; i<=n; i++){
cin >> step[i];
}
dp[1][0] = step[1];
for(int i=2; i<=n; i++){
dp[i][0] = max(dp[i-2][0], dp[i-2][1]) + step[i];
dp[i][1] = dp[i-1][0] + step[i];
}
cout << max(dp[n][0], dp[n][1]);
return 0;
}