알고리즘/BOJ
[BOJ 20159, Python 3] 동작 그만. 밑장 빼기냐?
70825
2021. 10. 4. 13:38
반응형
https://www.acmicpc.net/problem/20159
20159번: 동작 그만. 밑장 빼기냐?
카드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 단, N은 짝수이다. 둘째 줄에 카드의 윗장부터 밑장까지 카드의 값 X (1 ≤ X ≤ 10,000)이 정수로 주어진다.
www.acmicpc.net
대사만 들어봤지 밑장 빼기가 정확히 뭔지 몰라서 검색하다가 맨 윗장 다음장이 밑장으로 알고 풀었다가 계속 틀려버림
풀이
카드를 분배 할 때 밑장 빼기를 하면 맨 아래에 있는 카드를 줄 수 있다고 합니다.
그리고 카드를 분배한 사람(정훈이)부터 받을 수 있으니, 밑장 빼기를 하지 않으면 홀수번째로 나눠주는 카드는 정훈이가 가지고, 짝수번째로 나눠주는 카드는 상대방이 가져가는 것을 통해 짝수, 홀수로 나눈 누적합 알고리즘을 사용해야한다는 것을 알 수 있습니다.
이제 누적합인 것을 알았으니 짝수, 홀수로 나눈 누적합 배열을 1개씩 만들어줍니다. 그리고 홀수번째 카드는 정훈이가, 짝수번째 카드는 상대방이 받다가 밑장 빼기를 할 경우 정훈이는 다음장부터 원래 상대방이 받아야 할 카드들을 받게 되고, 상대방은 다음장부터 원래 정훈이가 받아야 할 카드들을 받게 됩니다.
밑장 빼기를 하는 순간 맨 밑에 있는 카드는 현재 차례인 사람한테 주고, 나머지는 누적합 배열들을 적절히 잘 사용해서 모든 경우의 수를 확인해주시면 됩니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
input = __import__('sys').stdin.readline
n = int(input())
x = [0] + [*map(int, input().split())]
odd_psum = [0]
even_psum = [0]
for i in range(1, n+1):
if i % 2:
odd_psum.append(x[i] + odd_psum[-1])
even_psum.append(even_psum[-1])
else:
odd_psum.append(odd_psum[-1])
even_psum.append(x[i] + even_psum[-1])
ans = odd_psum[-1]
for i in range(1, n+1):
if i % 2: val = odd_psum[i - 1] + (even_psum[-1] - even_psum[i])
else: val = odd_psum[i] + (even_psum[-2] - even_psum[i-1])
ans = max(ans, val)
print(ans)
|
cs |
반응형