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

문제로 가기

문제 소개, 아이디어

정훈이 -> 상대방의 순서로 카드를 윗장부터 하나씩 분배하고 있다.
카드 합이 더 큰 사람이 이긴다.
밑장 빼기를 최대 1번 해서, 정훈이가 얻을 수 있는 최대 카드 합을 구하는 문제이다.

밑장 빼기 최대 1번이니까 할 수도 있고, 안 할 수도 있는 것이다. 일단 안할 때 정훈이가 얻는 카드 합을 구했다. 그걸 ans에 대입했다. 그리고 밑장을 뺄 경우를 따져보면서, 각각의 상황에서 정훈이가 얻는 카드 합을 ans과 비교해서, 클 때의 값을 ans에 넣었다.
그러면 밑장 뺄 때 정훈이가 가진 카드의 합이 어떻게 되는지는 어떻게 구했을까?
일단 그림을 그려봤다 !

정훈이 차례에 밑장을 빼면, 그 때를 포함해서 이후의 원래 상대가 가질 예정이었던 카드의 합과 정훈이가 가질 예정이었던 카드의 합이 바뀐다.
맨 아래에서 상대, 정훈이 카드가 바뀌는 경우부터 시작해서 점점 위로 올라가면서, 서로 바뀔 카드의 합을 누적해가면서 비교했다.

처음에는 정훈이의 차례에만 밑장 빼기를 한다고 생각해서 틀렸다.
나중에 상대의 차례에도 밑장 빼기를 하는 경우를 생각해봤다. 상대방의 차례에서 밑장 빼기를 한다면, 그 때를 제외하고 이후의 정훈이- 상대방의 카드의 합이 바뀐다. 원래 맨 밑장은 상대방이 가질 카드니까(정훈이가 카드를 먼저 분배받기 시작하므로) 그 맨 밑장은 제외되는 것이다.

코드

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

# 밑장 빼기를 안했을 때 정훈이 카드의 합
junghun_origin_sum = 0
for i in range(N):
    if i % 2 == 0:
        junghun_origin_sum += arr[i]
ans = junghun_origin_sum
junghun_sum = junghun_origin_sum

# (정훈이 차례에서) 맨 아래에서부터 밑장 빼기 했을 때 합 어떤지
for i in range(N-1, 0, -2):
    junghun_sum += arr[i]
    junghun_sum -= arr[i-1]
    ans = max(ans, junghun_sum)


junghun_sum = junghun_origin_sum
# 상대 차례에서 맨 아래부터 밑장 빼기를 했을 때 합이 어떤지
for i in range(N-2, 1, -2):
    junghun_sum -= arr[i]
    junghun_sum += arr[i-1]
    ans = max(ans, junghun_sum)

print(ans)