[BOJ] 1912번 연속합(C++)

풀이 소요시간 : 40분

주어진 조건이 명확했고, 어떤 풀에서 어떤 최대값을 구해야하는지도 명확했지만 첫 접근을 잘못하는 바람에 엉뚱하게 시간을 많이 잡아먹었다. 접근 방법은 다음과 같다.

1. N 번째 수를 반드시 포함하는 경우
2. N 번째 수를 반드시 미포함하는 경우

N번째 수를 반드시 포함해야 하는 경우

1. N번째 수만 존재하거나
2. N-1번째 수를 반드시 포함하여야한다.

N번째 수를 반드시 미포함해야하는 경우 당연하게도

1. N-1번째 수가 반드시 포함되거나
2. N-1번째 수가 반드시 미포함된다.

이를 코드로 표현하면 다음과 같다.

전체 코드

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

int N;
int Map[100001];
int DP[100001][2];

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> Map[i];
	}
}

int main() {
	Input();

	DP[1][0] = Map[1];
	DP[1][1] = -987654321;

	DP[2][0] = max(Map[2], Map[1] + Map[2]);
	DP[2][1] = Map[1];

	for (int i = 3; i <= N; i++) {
		DP[i][0] = max(DP[i - 1][0] + Map[i], Map[i]);
		DP[i][1] = max(DP[i - 1][0], DP[i - 1][1]);
	}

	cout << max(DP[N][0], DP[N][1]) << '\n';
}