[BOJ 20159, Python 3] 동작 그만. 밑장 빼기냐?

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

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

대사만 들어봤지 밑장 빼기가 정확히 뭔지 몰라서 검색하다가 맨 윗장 다음장이 밑장으로 알고 풀었다가 계속 틀려버림

 

 

풀이

카드를 분배 할 때 밑장 빼기를 하면 맨 아래에 있는 카드를 줄 수 있다고 합니다.

그리고 카드를 분배한 사람(정훈이)부터 받을 수 있으니, 밑장 빼기를 하지 않으면 홀수번째로 나눠주는 카드는 정훈이가 가지고, 짝수번째로 나눠주는 카드는 상대방이 가져가는 것을 통해 짝수, 홀수로 나눈 누적합 알고리즘을 사용해야한다는 것을 알 수 있습니다.

 

이제 누적합인 것을 알았으니 짝수, 홀수로 나눈 누적합 배열을 1개씩 만들어줍니다. 그리고 홀수번째 카드는 정훈이가, 짝수번째 카드는 상대방이 받다가 밑장 빼기를 할 경우 정훈이는 다음장부터 원래 상대방이 받아야 할 카드들을 받게 되고, 상대방은 다음장부터 원래 정훈이가 받아야 할 카드들을 받게 됩니다.

 

밑장 빼기를 하는 순간 맨 밑에 있는 카드는 현재 차례인 사람한테 주고, 나머지는 누적합 배열들을 적절히 잘 사용해서 모든 경우의 수를 확인해주시면 됩니다.

 

 

코드

input = __import__('sys').stdin.readline
 
n = int(input())
x = [0] + [*map(int, input().split())]
odd_psum = [0]
even_psum = [0]
for i in range(1, n+1):
    if i % 2:
        odd_psum.append(x[i] + odd_psum[-1])
        even_psum.append(even_psum[-1])
    else:
        odd_psum.append(odd_psum[-1])
        even_psum.append(x[i] + even_psum[-1])
ans = odd_psum[-1]
for i in range(1, n+1):
    if i % 2: val = odd_psum[i - 1] + (even_psum[-1] - even_psum[i])
    else: val = odd_psum[i] + (even_psum[-2] - even_psum[i-1])
    ans = max(ans, val)
print(ans)