2021 KOI 예선 중2 결과

보이는 그대로 진출이 뜨긴 했는데.... 1교시보다 2교시가 더 높은 결과가 나왔다;;

1교시는 망해서 따로 설명은 안 하고

2교시에서 1번을 풀었는데

O(n)으로 완전 탐색을 돌렸다

import sys
import math
inf=math.inf
#sys.setrecursionlimit(10**9)
input=sys.stdin.readline
a=int(input())
l=list(map(int,input().split()))
st=[0]
ma=0
for i in range(a):st.append(st[i]+l[i])
for i in range(1,a-1):
    left=st[i+1]-l[0]
    right=st[a-1]-st[i]
    left1=st[a]-l[0]-l[i]
    right1=st[a]-st[i+1]
    left2=st[i]
    right2=st[a-1]-l[i]
    ma=max(ma,max([left+right,left1+right1,left2+right2]))
print(ma)

 

어떻게 O(n)에 완전 탐색이 되냐면 일단 움직이는 점을 A, B라고 하고 도착지점을 C라고 했을 때 위치가 A와 B가 모두 C의 왼쪽이나 오른쪽에 있거나 A와 B사이에 C가 있는 경우로 나뉘는데 이때 A와 B사이에 있는 경우 값이 모두 양수이기 때문에 A와 B는 가장 끝의 값을 고르는 게 최대이다. 이제 한쪽으로 밀리는 경우를 따져야 되는데 이때 A와 C를 바꿨을 때와 B와 C를 바꿨을 때의 값을 구하면 된다. 한쪽으로 밀렸을 때는 A 또는 B가 한쪽 끝에 있고 그 사이에 다른 점이 있어야 되는데 그걸 O(n)으로 중앙값을 바꿔주는 동시에 중앙값에 다른 점을 놨을 때의 경우를 구해주면 최댓값을 구해줄 수 있다.

 

본선전까지 틈틈이 연습해서 nypc때 좋은 결과를 내고 정 올본 선도 좋은 결과를 낼 것이다.