이코테 DP : 개미 전사 [C++]

다이나믹 프로그래밍으로 해결할수 있는 문제이다. 

개미전사가 주어진 식량창고에서 얻을 수 있는 식량 최댓값을 구하는 문제인데 

그리디나 구현으로 푸는 것보다 작은 요소의 해결책을 쌓아서 큰문제의 해결책을 찾는 다이나믹 프로그래밍이 훨씬 효율적인 문제다.

 

바텀업 방식으로 해결했다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

int d[100];
int N;
vector<int> arr;

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		arr.push_back(x);
	}

	d[0] = arr[0];
	d[1] = max(arr[0], arr[1]);
	for (int i = 2; i < N; i++) {
		d[i] = max(d[i - 1], d[i - 2] + arr[i]);
	}

	cout << d[N - 1] << '\n';

	return 0;
}