[골드 4] 백준 20159 - 동작 그만. 밑장 빼기냐?

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

풀이

플레이어가 번갈아 가면서 카드를 가져간다.

짝수 번째(0, 2, 4 … )는 내차례, 홀수 번째는 상대 차례이다.

마지막 카드 1장을 상다 차례에서 내가 가져도록 1번의 밑장 빼기를 허용한다.

최대 점수를 얻기 위해 밑장 빼기를 어느 위치에서 할지를 결정해야한다.

psum0 = [0] * N  # 내 차례에서의 누적합
psum1 = [0] * N  # 상대 차례에서의 누적합

psum0[0] = A[0]
psum1[0] = 0

for i in range(1, N):
    if i % 2 == 0:  # 내 차례
        psum0[i] = psum0[i - 1] + A[i]
        psum1[i] = psum1[i - 1]
    else:           # 상대 차례
        psum0[i] = psum0[i - 1]
        psum1[i] = psum1[i - 1] + A[i]

i번째 카드가 내 차례인지 상대 차례인지를 나누어 각각의 누적합 배열을 구성한다.

def range_sum0(l, r): ...
def range_sum1(l, r): ...

누적합을 이용한 구간 합 함수를 각각 구현한다.

sum0의 경우 내 차례인 카드들 중 l ~ r의 합을 나타내고, sum1의 경우 상대 차례인 카드들 중 l ~ r의 합을 나타낸다.

밑장 빼기 시뮬레이션은 다음과 같이 진행한다.

answer = psum0[N - 1]  # 밑장 안 뺐을 경우의 기본 점수

for i in range(N):
    score = range_sum0(0, i - 1) + range_sum1(i, N - 2)
    if i % 2 == 0:
        score += A[N - 1]  # 밑장 빼기 성공하면 마지막 카드 얻음
    
    answer = max(answer, score)

i는 밑장을 빼는 위치이고, range_sum0, range_sum1을 통해서 밑짱 빼기 시뮬레이션을 진행한다.

코드

# 백준 20159 - 동작 그만. 밑장 빼기냐?
# 분류 : 누적합

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

psum0 = [0] * N
psum1 = [0] * N
psum0[0] = A[0]
psum1[0] = 0

for i in range(1, N) :
    if i % 2 == 0 :
        psum0[i] = psum0[i - 1] + A[i]
        psum1[i] = psum1[i - 1]
    else :
        psum0[i] = psum0[i - 1]
        psum1[i] = psum1[i - 1] + A[i]

def range_sum0(l, r) :
    if l > r :
        return 0
    ret = psum0[r]
    if l > 0 :
        ret -= psum0[l - 1]
    return ret

def range_sum1(l, r) :
    if l > r :
        return 0
    ret = psum1[r]
    if l > 0 :
        ret -= psum1[l - 1]
    return ret

answer = psum0[N - 1]
for i in range(N) :
    score = range_sum0(0, i - 1) + range_sum1(i, N - 2)
    if i % 2 == 0 :
        score += A[N - 1]
    
    answer = max(answer, score)

print(answer)