[BOJ] 20159 - 동작 그만. 밑장 빼기냐?

[백준] 20159 - 동작 그만. 밑장 빼기냐?

DP문제로 오해할 수 있지만 DP를 사용할 필요 없이 구간합 배열을 이용하면 되는 문제다.
반드시 두 사람이 번갈아서 카드를 나누어 갖고, 밑장빼기가 일어나는 단 한 번을 제외한다면 모두 위에서부터 카드를 가져가기 때문이다.
따라서 홀수번째 인덱스만 더한 구간합 배열과 짝수번째 인덱스만 더한 구간합 배열 두 개를 가지고 n가지의 밑장을 빼는 경우의 수에 대해 최대 점수를 갱신한다면 답을 구할 수 있다.

소스코드

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

ll n, card[100005], odd[100005], even[100005];

int main(void) {
	scanf("%lld", &n);
	for (ll i = 1; i <= n; i++) {
		scanf("%lld", card + i);
		if (i % 2) {
			odd[i] = odd[i - 1] + card[i];
			even[i] = even[i - 1];
		}
		else {
			odd[i] = odd[i - 1];
			even[i] = even[i - 1] + card[i];
		}
	}
	ll ans = odd[n];
	for (ll i = 1; i < n; i++) {
		if (i % 2) {
			ans = max(ans, odd[i - 1] + even[n - 1] - even[i] + card[n]);
		}
		else {
			ans = max(ans, odd[i - 1] + even[n - 1] - even[i - 1]);
		}
	}
	printf("%lld", ans);
	return 0;
}