BOJ 20159 : 동작 그만. 밑장 빼기냐?

• 문제 링크 : boj.kr/20159
• 난이도 : G4
• 태그 : 누적합

20159번: 동작 그만. 밑장 빼기냐?

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<ll> arr(n+1);
    vector<ll> odd(n+1), even(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        if(i%2) odd[i] = arr[i];
        else even[i] = arr[i];
        odd[i] += odd[i-1];
        even[i] += even[i-1];
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ll temp = 0;
        temp += odd[i-1];
        temp += even[n]-even[i-1];
        if(i%2==0) temp -= arr[n];
        ans = max(ans, temp);
    }
    cout << ans;

    return 0;
}

---

풀이

정훈이는 밑장을 빼기 이전에는 홀수번째 카드, 밑장을 뺀 이후에는 짝수번째 카드를 가지게 된다. 어느 한 시점을 기준으로 앞 뒤의 홀수번째, 짝수번째 카드의 합을 알고 있으면 되니 짝, 홀을 나누어 누적합 배열을 구해둔다.

홀수번째 밑장빼기를 할 경우(정훈이가 밑장을 가질 경우), 짝수번째 밑장빼기를 할 경우(상대방이 밑장을 가질 경우)를 나누어 상상한 뒤 누적합 배열을 이용하면 풀 수 있다.