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

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

 

문제

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

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

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

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

입력

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

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

 

출력

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

코드

n = int(input())
x = list(map(int, input().split()))

odd = [0] * (n//2+1)
even = [0] * (n//2+1)
for i in range(0, n, 2):
    even[i//2+1] = even[i//2] + x[i]
    odd[i//2+1] = odd[i//2] + x[i+1]

ans = 0
for i in range(n):  # i번째 카드에서 밑장을 뺀다면
    if i % 2 == 0:
        ans = max(ans, even[i//2]+(odd[-1]-odd[i//2]))
    else:
        ans = max(ans, even[i//2+1]+(odd[-2]-odd[i//2]))
print(ans if ans != 0 else even[-1])

 

편의상 0은 짝수라고 할 때, 밑장빼기를 하지 않고 카드를 분배하면 짝수는 정훈이가, 홀수는 상대방이 가져가게 된다. 

 

한 번 밑장빼기를 한다면 정훈이가 홀수, 상대방이 짝수를 가져가게 될 것이다. 그렇기 때문에 남은 홀수 카드의 합이 짝수 카드의 수의 합보다 커지는 순간에 밑장을 빼줘야 정훈이가 카드의 합을 더 크게 가질 수 있다.

짝수, 홀수 카드의 i번째까지의 합이 필요하기 때문에 odd, even 2개로 나누어 카드의 합을 저장해두었다. 이 값을 가지고 몇번째에서 밑장을 빼야 카드의 합이 최대가 될 지 구해볼 것이다.

 

그런데 이때 주의해야 할 점은 정훈이 차례에 밑장을 빼는 것과 상대방 차례에 밑장을 빼는 것은 계산이 조금 다르다는 점이다. 아래 그림을 참고하면 더 쉽게 이해할 수 있다.

어느 차례에 밑장을 빼든 '나'가 갖고 가던 카드가 짝수->홀수로 바뀌는 것은 변함이 없다. 그렇지만 '나' 차례에 밑장을 빼면 가장 마지막 카드까지 '나'가 갖고 가면 되는데, '너' 차례에 밑장을 빼면 '나'는 가장 마지막 카드를 제외하고 홀수 카드들을 갖고 가야 한다.

이렇기 때문에 짝수번째(나)에 밑장 뺄 때와 홀수번째(너)에 밑장을 뺄 때 2가지 경우로 나누었다.