[백준] 20159번: 동작 그만. 밑장 빼기냐? (python)

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

---

문제 )

 

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

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

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

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

 

 

 

입력 :

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

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

 

 

출력 :

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

 

 

 

풀이)

 

제목만 보고 만만해보여서 덤볐다가 큰 코 다친 문제이다.

누적합에 대해서 다시 한번 공부해야겠다는 생각이 들었다.

 

n = int(input())
li = list(map(int, input().split()))
 
origin = 0
for i in range(n)[::2]:
    origin += li[i]
ans = origin
 
j_sum = origin
# 상대방 차례에 밑장빼기를 했을 때,
for i in range(n - 2, 1, -2):
    j_sum -= li[i]
    j_sum += li[i - 1]
    ans = max(ans, j_sum)
"""
기존 =>  1회  => 2회
3 2     3 2     3 3v    
5 2     5 3v    2 5
1 3v    2 1     3 2
 9       10      8
"""
 
 
j_sum = origin
# 정훈이 차례에 밑장빼기를 했을 때,
for i in range(n - 1, 0, -2):
    j_sum += li[i]
    j_sum -= li[i - 1]
    ans = max(ans, j_sum)
"""
기존 =>  1회 =>  2회  => 3회
3 2     3 2     3 2    v3 3
5 2     5 2    v3 5     2 5
1 3    v3 1     2 1     2 1
 9       11      8       7
"""
print(ans)

---

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

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