[백준] 23023 - 서프라이즈

문제 링크

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

문제 요약

 

• 연속된 학번의 학생 구간을 선택하고 두 그룹으로 나눠 각 그룹의 스테이크 무게 합의 차 E를 계산합니다.
• E가 최소가 되는 두 그룹의 스테이크 무게 합이 가장 큰 경우를 찾습니다.
• 해당 경우의 스테이크 무게 합을 출력합니다.

 

푼 방법

• 누적합 계산: presum 배열을 만들어 스테이크 무게의 누적합을 저장하여 특정 구간의 합을 빠르게 구합니다.
• 구간 선택 및 이진 탐색:
  • 두 그룹의 스테이크 무게 합 차이를 최소화하기 위해 이진 탐색을 사용하여 구간의 중간 지점을 조절합니다.
  • EEE가 최소인 경우를 찾으면서, 만약 EEE가 동일하면 두 그룹의 무게 합이 최대인 경우를 선택합니다.

 

정답 코드

import sys
n = int(sys.stdin.readline().rstrip())
steaks = [0] + list(map(int, sys.stdin.readline().split()))
presum = [0] * (n+1)

for i in range(1, n+1):
    presum[i] = presum[i-1] + steaks[i]

minE=float('inf')
ans = 0

for i in range(1, n+1):
    for j in range(i+1, n+1):
        l = i
        r = j        
        while l<=r:
            mid = (l+r)//2
            lsum = presum[mid] - presum[i-1]
            rsum = presum[j] - presum[mid]
            E = abs(lsum - rsum)
            
            if E < minE or (E == minE and lsum+rsum > ans):
                minE = E
                ans = lsum + rsum
            if lsum == rsum:
                break
            elif lsum < rsum:
                l = mid+1
            else:
                r = mid-1

print(ans)