(Python/🥇4)백준알고리즘 20159번: 동작 그만. 밑장 빼기냐 ?

문제 바로가기 

동작 그만, 밑장 빼기냐 ?

 

문제:

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

입력:

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

출력:

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

 

풀이:

 

손으로 그림으로 그렸을때는 쉬워보이지만 구현이 좀 어려웠던 것 같다.

 

import sys
from collections import deque

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n = int(input())
x = deque(list(map(int, sys.stdin.readline().split(" "))))
# 밑장 빼기는 한번.

# 밑장 안뺌
dp = 0
for i in range(0, n, 2):
    dp += x[i]
result = dp
dp1 = dp2 = dp
for i in range(n - 1, 0, -1):
    # 내가 밑장.
    if i % 2:
        dp1 += x[i]
        dp1 -= x[i - 1]
    # 니가 밑장
    else:
        dp2 -= x[i]
        dp2 += x[i - 1]
    result = max(dp1, dp2, result)
print(result)

 

밑장빼기를 안한경우 vs 밑장빼기 한 패가 나한테 온 경우, 밑장빼기한 패가 상대한테 준 경우 3개로 나누어서

최댓값을 계속 바꿔주면된다.

 

result = 밑장 x

dp1 = 밑장 나한테옴

dp2 = 밑장 너한테 줌