백준 알고리즘 20159번 : 동작 그만. 밑장 빼기냐? 파이썬 코드 <문제풀이>

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

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

# brute-force + prefix-sum
N=int(input())
cards=list(map(int,input().split()))

zzak_sum=[0]*(N//2+1)
hol_sum=[0]*(N//2+1)
for i in range(N):
    ii=i//2+1
    if i%2==0:
        zzak_sum[ii]=zzak_sum[ii-1]+cards[i]
    else:
        hol_sum[ii]=hol_sum[ii-1]+cards[i]

ans=0
for i in range(0,N//2+1):
    # my mit_zzang
    front=zzak_sum[i]
    back=hol_sum[-1]-hol_sum[i]
    ans=max(ans,front+back)

    # his mit_zzang
    front=zzak_sum[i]
    back=hol_sum[-2]-hol_sum[i-1]
    ans=max(ans,front+back)
    
print(ans)

 

 

 

 

 

9달 전에 도전했다가 엣지 케이스를 찾지 못해 포기한 문제입니다. 그래서 알고리즘 분류를 먼저 보고 풀었네요.

시간 제한과 메모리 제한이 아주 널널한 문제입니다. (2초, 1024MB)

 

누적합을 짝수 번째와 홀수 번째 인덱스로나눠서 2개의 리스트로 만들고 적당히 조합해서 답을 내면 되었습니다.

 

처음에는 카드를 나눠주는 친구가 카드를 받을 때만 밑장빼기가 가능한 줄 알았는데, 상대방이 받을 때도 밑장에서 꺼내줄 수 있다는 것을 알게 되었습니다.

 

그래서 가장 마지막 for문에 'my mit_zzang'(내 순서 밑장)과 'his mit_zzang'(상대 순서 밑장) 이 나뉘어있습니다.

 

간만에 머리에 쥐가 좀 났던 문제입니다..