[백준] 20159번 : 동작 그만. 밑장 빼기냐? (C++)

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

---

문제)

싸늘하다. 정훈이는 다음과 같은 도박을 하고 있다.

 

N개의 카드와 2명의 플레이어가 있다. 플레이어가 자신과 상대방에게 번갈아 가며 카드의 윗장부터 한 장씩 분배한다. 단, 카드는 분배한 사람부터 받는다. 카드를 모두 분배했을 때 카드에 적힌 수의 합이 더 큰 사람이 이긴다. 두 명이 공평하게 카드를 나눠 갖기 위해 카드의 개수는 짝수로 주어진다.

 

카드를 섞고 있는 정훈이는 타짜다. 수없이 많이 카드를 섞어본 경험으로 섞고 난 후 카드의 값들을 다 알고 있다. 정훈이에게 카드를 분배할 수 있는 기회가 왔다. 확실한 승리를 위해 카드를 분배할 때 카드의 윗장이 아닌 밑장을 빼는 밑장 빼기를 하기로 마음을 먹었다. 상대는 눈치가 빠르기로 유명한 선수이므로 밑장 빼기는 최대 한번 할 것이다.

 

정훈이가 최대 한번 밑장 빼기를 할 때 얻을 수 있는 최대 카드의 합을 구하여라.

 

 

 

입력 :

카드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 단, N은 짝수이다.

둘째 줄에 카드의 윗장부터 밑장까지 카드의 값 X (1 ≤ X ≤ 10,000)이 정수로 주어진다.

 

 

 

출력 :

정훈이가 얻을 수 있는 최대 카드 값의 합을 출력한다.

 

 

 

 

 

풀이)

 

// 20159. 동작 그만. 밑장 빼기냐?
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    vector<int> prefix_odd(n + 1, 0);
    vector<int> prefix_even(n + 1, 0);
 
    int temp;
    for (int i = 1; i < n + 1; i++)
    {
        cin >> temp;
 
        prefix_odd[i] = prefix_odd[i - 1];
        prefix_even[i] = prefix_even[i - 1];
 
        if (i % 2 == 0) prefix_even[i] += temp;
        else prefix_odd[i] += temp;
    }
 
    int ans = 0;
    for (int i = 1; i < n + 1; i++)
    {
        int result = 0;
        // i가 짝수일 경우 마지막 패를 상대에게 준다.
        if (i % 2 == 0)
        { 
            result = prefix_odd[i] + (prefix_even[n - 1] - prefix_even[i - 1]);
        }
        // i가 홀수일 경우 마지막 패를 내가 가진다.
        else
        {
            result = prefix_odd[i - 1] + (prefix_even[n] - prefix_even[i]);
        }
 
        ans = max(ans, result);
    }
 
    cout << ans;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/20159 

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