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

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

시간 제한 2초, 메모리 제한 1024MB

# 조건

• 정훈이는 다음과 같은 도박을 하고 있다.
• N개의 카드와 2명의 플레이어가 있다.
• 플레이어가 자신과 상대방에게 번갈아 가며 카드의 윗장부터 한 장씩 분배한다.
  • 단, 카드는 분배한 사람부터 받는다.
• 카드를 모두 분배했을 때 카드에 적힌 수의 합이 더 큰 사람이 이긴다.
• 두 명이 공평하게 카드를 나눠 갖기 위해 카드의 개수는 짝수로 주어진다.
• 카드를 섞고 있는 정훈이는 타짜다.
• 수없이 많이 카드를 섞어본 경험으로 섞고 난 후 카드의 값들을 다 알고 있다.
• 정훈이에게 카드를 분배할 수 있는 기회가 왔다.
• 확실한 승리를 위해 카드를 분배할 때 카드의 윗장이 아닌 밑장을 빼는 밑장 빼기를 하기로 마음을 먹었다.
• 상대는 눈치가 빠르기로 유명한 선수이므로 밑장 빼기는 최대 한번 할 것이다.
• 정훈이가 최대 한번 밑장 빼기를 할 때 얻을 수 있는 최대 카드의 합을 구하여라.

입력

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

출력

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

# 접근 방법

• 밑장 빼기를 하는 경우는 내가 받는 경우 또는 상대방에게 주는 경우이다.
• 또한, 밑장 빼기를 한 후에는 나눠지는 카드 순서가 뒤바뀌는 것을 처음에 생각하지 못하여 틀렸습니다를 받았다.
• 최초 누적합의 값을 res로 설정한 후 정훈이의 차례와 상대방의 차례에서 맨 아래부터 밑장 빼기를 했을 때 합이 어떤지 비교해준 후 출력하면 된다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))

prefix = 0
for i in range(0, N, 2):
    prefix += nums[i]

result = prefix
# 나의 입장과 상대 입장에서 밑장 빼기 하며 비교
val1 = val2 = prefix
for i in range(N-1, 0, -1):
    if i%2:
        val1 += nums[i]
        val1 -= nums[i-1]
    else:
        val2 -= nums[i]
        val2 += nums[i-1]
    result = max(val1, val2, result)

print(result)