풀이 전략

1) 경우의 수 모두 다 따져가면서 진행하려고 했다.
하지만 n의 크기는 최대 100이므로, 경우의 수가 엄청 많아지므로,
접근법이 잘못됨. 다르게 생각해보자.

2) 일단 인덱스 하나하나 마다 값이 어떻게 결정되는지 생각을 해보앗따.
1[0] , 3[1] , 1[2] , 5[3] 이렇게 있을 경우

[1] 값은 1[0] vs 3[1]을 비교했을때 3이 크므로
[1]값은 3으로 갱신된다.
-> 변수를 두개 사용해야 겠다 생각함.

arr[] 과 dp[]로 구분함. arr은 입력되는 값이고, dp[]는 갱신값으로

dp[2]
-> arr[2] + dp[0]
-> 이전값 dp[1]
두 개 중에서 가장 큰값을 선택하면 된다.

끄적끄적

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main() {

	int n;
	cin >> n;

	vector<int>dp(n + 1, 0);
	vector<int>arr(n + 1, 0);
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	dp[0] = arr[0];
	dp[1] = max(dp[0], arr[1]);

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

	return 0;
}