20159(동작 그만. 밑장 빼기냐?) - 해결

동작 그만. 밑장 빼기냐?

 

문제

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

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

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

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

 

입력

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

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

 

출력

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

---

차례대로 패를 받기 때문에 밑장 빼기를 해서 내가 가지면 상대가 받아야 하는 걸 내가 받게 된다는 것을 알게 되어서 

홀수 번째 카드를 내가 가지다가 밑장 빼기를 하면 짝수 번째 카드를 내가 가지게 된다.

그래서 순서를 처음부터 밑장 빼기를 한 거부터 차례대로 구하려고 하였다.

순서를 보면 짝수의 패를 모두 더한 거부터 홀수 패를 더하고 짝수 패를 빼는 식으로 구하였다.

하지만,

이렇게만 하면 11 퍼쯤에서 계속 틀리는데 계속 찾아보니깐 밑장 빼기를 상대한 테하는 것을 생각을 안 했다.

그 경우는 밑장 빼기를 안 한 거와 끝에서 밑장 빼기 한 거부터 앞에서 한 거까지로 구하였다.

해당 예시

6
3 2 5 7 3 1

답 : 15

import sys
input = sys.stdin.readline

N  = int(input())

# 홀수, 짝수번째 패
A = []
B = []

_list = list(map(int,input().split()))

# 홀수, 짝수 나눠서 담기
for i in range(N):
    if i % 2:
        B.append(_list[i])
    else:
        A.append(_list[i])

# 나한테 밑장 빼기했을 때, 
# 처음부터 밑장 빼기를 한거부터 차례로
me_list = [sum(B)]
# 상대에게 밑장 빼기했을 때,
# 밑장빼기 안한거와 끝에서 부터 밑장빼기한거 부터 앞으로
you_list = [sum(A)]

# 상대와 나에게 한번씩 밑장 빼기한 것을 저장
for i in range(1,N//2):
    # 앞으로 가면서 밑장빼기하는 인덱스를 늘리면
    # A에꺼는 더하고 B에꺼는 뺀다.
    me_list.append(me_list[i-1] + A[i-1] - B[i-1])
    # 끝에서 부터 밑장 빼기를하면 그 인덱스의 A는 빼고 B를 더해준다.
    you_list.append(you_list[i-1] - A[N//2 - i] + B[N//2 - i - 1])

# 그 중에 가장 큰거
print(max(me_list+you_list))