[C++] 백준 2579번 문제풀이++] 백준 2579번 문제풀이

이 문제를 DFS 로 풀려고 했는데

시간초과가 뜨고 DFS로 풀지 못하였다.

문제를 풀 때 DP를 써야하는데

DP의 중점은 큰 문제를 작은 문제로 분할하여 푼다.

이것을 중점으로 풀자.

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int main() {
	int cnt;
	cin >> cnt;
	int arr[300];
	int now[300] = { 0, };
	for (int i = 0; i < cnt; i++)
		cin >> arr[i];
	now[0] = arr[0];
	now[1] = max(arr[1], arr[0] + arr[1]);
	now[2] = max(arr[2] + arr[0], arr[1] + arr[2]);
	for (int i = 3; i < cnt; i++)
		now[i] = max(arr[i] + now[i - 2], arr[i] + arr[i - 1] + now[i - 3]);
	cout << now[cnt-1];
}