[백준 15554번] 전시회 (Python3)

import sys
input = sys.stdin.readline

N = int(input())
art = sorted([*map(int,input().split())] for i in range(N))

S = sum(art[i][1] for i in range(N))+art[0][0]-art[-1][0]

prefix1 = [0]; prefix2 = [0]
for i in range(N-1):
  prefix1.append(prefix1[-1]+art[i+1][0]-art[i][0]-art[i][1])
  prefix2.append(prefix2[-1]+art[-i-1][0]-art[-i-2][0]-art[-i-1][1])

arr1 = [(0,-1)]; arr2 = [(0,N)]
for i in range(1,N):
  if prefix1[i] > arr1[-1][0]:
    arr1.append((prefix1[i],i-1))
  if prefix2[i] > arr2[-1][0]:
    arr2.append((prefix2[i],N-i))
arr2.reverse()

MAX = 0; j = 0
for s,i in arr1:
  for j in range(j,len(arr2)):
    if arr2[j][1] <= i+1:
      continue
    MAX = max(MAX,s+arr2[j][0])
    break
print(S+MAX)

누적합+스택을 이용하여 해결하였다.

 

풀이를 설명하면,

1. 모든 미술품이 포함되었을 때의 가치를 구하고, 미술품은 크기순으로 정렬한다.

2. 누적합을 이용하여 prefix1에는 미술품의 전체가치에서 1~i까지의 미술품을 제거했을 때 가치의 변화량을, prefix2에는 i~N까지의 미술품을 제거했을 때 가치의 변화량을 저장한다.

3. arr1과 arr2에 prefix1, prefix2에서 가치의 변화량이 이전보다 클 때와 그때의 인덱스 i를 순서대로 저장한다.

4. MAX를 0으로 시작해서 arr1의 첫번째부터 시작해서 만약 arr1의 가치변화량과 인덱스가 s,i라면 arr2에서 i+2 이상의 인덱스를 가진 값 중 가장 큰 값일때로 MAX를 갱신한다. (i+2 이상인 이유는 앞에서부터 i까지 제거했다면 i+1은 남겨두어야 하기 때문)

5. 모든 미술품이 포함되었을 때의 가치 + MAX를 출력한다.

 

풀이 자체는 간단한데, 인덱스를 처리하는 과정에서 실수가 많이 나왔던 문제였다.

 

 

오늘의 교훈) 실수를 줄이자.