백준 20159 동작 그만. 밑장 빼기냐? Python

🐸 문제 정보

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

 

🤖 알고리즘

누적합

 

⏱️ 풀이 시간

47.56m

 

📝 풀이

구현이 껴있는 누적합 문제였다.

문제를 읽자마자 누적합으로 풀어야한다는 것은 바로 알았으나, 이를 구현해내기까지 조금 헤맸다.

헤맨 이유는 '상대의 패도 밑장 뺄 수 있다' 라는 전제 때문이었다.

문제에 전혀 명시가 안되어있고, 마치 내 패에서 밑장을 뺄 수 있는 것처럼 작성되어있지만, 상대에 패에서도 밑장을 뺼 수 있음을 알아야 한다.

 

1. 홀수 인덱스끼리, 짝수 인덱스끼리 누적합을 구해서 한 리스트에 넣는다.
   • 이 때 누적합 리스트의 0, 1 인덱스는 0으로 채운다 (계산을 편하게 하기 위해)
2. 특정 인덱스에서 밑장을 빼는 경우를 구해야한다.
   • 짝수 인덱스(정훈이의 패)에서 밑장을 빼는 경우 p[i - 2] + last + (p[-3] - p[i - 1])
   • 홀수 인덱스(상대의 패)에서 밑장을 빼는 경우 p[i - 1] + (p[-3] - p[i - 2])
   • p => 누적합 리스트
   • last => 마지막 카드 (밑장)

저러한 계산식이 나오는 이유는 꽤 직관적이다.

 

정훈이의 패를 놓을 때 밑장을 빼는 경우는,

이전까지 정훈이의 패의 합(p[i - 2])에 밑장(last)를 더하고, 다음 차례에 정훈이가 가질 카드(p[i + 1]) ~ 밑장 뺀 후에 정훈이가 가질 마지막 카드(p[-3])까지의 합(p[-3] - p[i - 1])이다. 누적합에 의해서 p[-3] - p[i+1]이 아닌 p[-3] - p[i - 1]이다.

 

반대로 상대의 패를 놓을 때 밑장을 빼는 경우에도 정훈이의 카드 합만 생각해야된다.

상대의 패에서 밑장을 빼면, 기존에 상대가 가져가야했을 카드를 정훈이가 가져가고, 그 이후 부터 2씩 뛰면서 마지막까지 가기 때문에, 현재 카드 직전까지 정훈이의 카드 합(p[i - 1])과 다음 차례에 정훈이가 가질 카드(p[i]) ~ 밑장 뺀 후에 정훈이가 가질 마지막 카드(p[-3])까지의 합(p[-3] - p[i - 2])이다. 마찬가지로 누적합에 의해 p[-3] - p[i]가 아닌 p[-3] - p[i - 2]이다.

 

뭔가 항상 PS 리뷰 보면 공식을 어렵게 써놔서 짜증났었는데, 나도 어렵게 쓴 것 같아서... 좀 그렇다.

코드를 보면..! 이해가 될..거다..!

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
cards = list(map(int, input().rstrip().split()))
prefix = [0, 0]

for i in range(n):
    prefix.append(prefix[i] + cards[i])

res = prefix[-2] # 초기값 -> 밑장을 안 뺸 경우
for i in range(2, n + 2):
    val = 0
    if i % 2 == 0:
        val = prefix[i - 2] + cards[-1] + prefix[-3] - prefix[i - 1]
    else:
        val = prefix[i - 1] + prefix[-3] - prefix[i - 2]
    res = max(res, val)

print(res)