누적합(서프라이즈~/G3) - 23032

1. 문제

쿠기는 가톨릭대학교 컴퓨터정보공학부 학부장이다. 곧 다가오는 시험 기간에 학생들에게 힘을 주고자 간식 행사에 안심 스테이크를 주려고 한다.
컴퓨터정보공학부에는 N명의 학생이 있는데, 학생들은 1부터 N까지 고유한 학번이 부여되어있다. 쿠기는 N명의 학생을 대상으로 스테이크 몇 그램을 먹고 싶은지 설문 조사를 했다. 설문 조사를 마치고 학생들의 설문 결과를 본 쿠기는 경악했다. 이 설문 조사 결과를 기반으로 간식 행사를 진행한다면 다시는 간식 행사를 할 수 없다. 이미 간식 행사 홍보를 하여 주목을 받은 쿠기는 돌이킬 수 없어서 전부 다 주려고 했던 간식을 이벤트처럼 위장하려고 한다.
이벤트의 내용은 다음과 같다.
 
서프라이즈! 다음과 같은 조건을 만족하는 학생들에게 스테이크를 드려요!
1. 임의로 연속된 학번의 학생들을 정해요!
2. 임의로 대상 학생들을 두 그룹으로 나눠요! 대신 한 그룹의 학생들은 학번이 인접해야 해요! 그룹에는 최소 한명의 학생이 있어야 해요!
3. 두 그룹의 스테이크 무게 합의 차 E를 구해요! E를 계산할 때는 합이 큰 그룹에서 작은 그룹의 합을 빼요!
4. 가능한 모든 경우에 대해 계산하여 E가 최솟값인 두 그룹의 학생들에게 스테이크를 드립니다!
5. 대신 최솟값이 같은 경우가 여러 가지라면 두 그룹의 스테이크 무게 합이 가장 큰 두 그룹의 학생들에게 스테이크를 드립니다!

예를 들면, 1번~6번 학생에 대한 설문 조사 결과가 [2, 1, 5, 2, 4, 4]일 때 다음과 같이 계산한다.

1. 임의로 연속되게 학번이 2인 학생부터 6인 학생까지 정한다.
2. 임의로 2~3번 학생의 그룹과 4~6번 학생의 그룹을 나눈다.
3. 2~3번 학생 그룹의 합은 6, 4~6번 학생 그룹의 합은 10이므로 E는 4이다.
4. 가능한 모든 경우에 대해 계산한다.
5. 해당 예시에 대한 답은 2~4번 학생 그룹과 5~6번 학생 그룹일 때 E가 최소이므로 2~6번 학생이 이벤트 당첨자다.

쿠기는 한시름 놨지만, 스테이크를 구매하기 위해 이벤트 당첨자들의 스테이크 무게의 합을 구하는 코드를 작성하려고 했는데 노트북이 망가졌다.
쿠기를 도와 당첨자들의 스테이크 무게 합을 구하는 프로그램을 작성하시오.
 

2. 입력

첫째 줄에 정수 N(2 ≤ N ≤ 2,000)이 주어진다.
다음 줄에 1번 학생부터 N번 학생까지 차례대로 설문 조사에 적은 스테이크의 무게를 나타내는 정수 W(1 ≤ W ≤ 10,000)가 주어진다.

6
2 1 5 2 4 4

 

6
5 10 5 3 20 11

 

3. 출력

이벤트에 당첨된 학생들의 스테이크 무게 합을 출력한다.

16

 

38

 

4. 코드

import sys

input = sys.stdin.readline
n = int(input())
weight = list(map(int, input().split()))

result = 0
minVal = 1e9
# 좌 : 0 / 우 : 누적합
lt, rt = 0, sum(weight)

# 최소값이 같은 그룹이 존재하면 무게합이 높은 두그룹의 합을 반환
def resultChk(c, m, r, s):
  # c:그룹차, m:그룹차최소값, r:그룹합최댓값, s:그룹합
  if c == m:
    return m, max(r, s)
  elif c < m:
    return c, s
  else:
    return m, r

for i in range(n):
  # 좌,우 초기 인덱스
  l, r = -1, n
  # 좌,우 누적합
  lt, rt = lt + weight[i], rt - weight[i]
  # 좌,우 초기 누적합
  left, right = lt, rt
  while l < n - 1 and l + 1 < r:
    # 좌측 그룹합이 우측그룹합보다 작을 때
    if left < right:
      r -= 1
      minVal, result = resultChk(right - left, minVal, result, left + right)
      right = right - weight[r]
    # 좌측 그룹합이 우측그룹합보다 클 때
    elif left > right:
      l += 1
      minVal, result = resultChk(left - right, minVal, result, left + right)
      left = left - weight[l]
    # 우측 누적합과 좌측 누적합이 같을 때
    else:
      minVal, result = resultChk(0, minVal, result, left + right)
      break      
print(result)

 

5. 풀이설명

① 입력값 n과 weight list를 입력 받는다.

② 결과값 result와 최소값을 담을 minVal을 각각 0, 1e9로 생성한다.

③ 좌측 그룹의 무게합 lt 와 우측 그룹의 무게합 rt를 각각 0, weight의 전체합으로 생성한다.

③ n만큼 반복문을 실행하는데 좌측 그룹의 인덱스 l과 우측 그룹의 인덱스 r, 좌측 그룹의 구간합 left와 우측 그룹의 구간합 right을 각각 i, n, lt + weight[i], rt - weight[i]로 생성한다.

④ l(좌측 인덱스) 가 n-1보다 크거나 l+1이 r(우측 인덱스)보다 커질때까지 while 반복문을 실행한다.

-  left(좌측 그룹합)가 right(우측 그룹합)보다 작은 경우

  ⓐ r을 1만큼 감소한다.

  ⓑ resultChk(right - left, minVal, result, left + right)를 실행하여 minVal과 result에 대입

  ⓒ right에서 weight[r]을 감소한다.

 

- left(좌측 그룹합)가 right(우측 그룹합)보다 큰 경우 

  ⓐ l을 1만큼 감소한다.

  ⓑ resultChk(left-right, minVal, result, left + right)를 실행하여 minVal과 result에 대입

  ⓒ left에서 weight[l]을 감소한다.

 

- left(좌측 그룹합)와 right(우측 그룹합)이 같은 경우 

  ⓐ minVal, result = resultChk(0, minVal, result, left + right) minVal과 result에 대입

  ⓑ break문 실행

 

⑤ resultChk 함수 : c:그룹차, m:그룹차최소값, r:그룹합최댓값, s:그룹합를 인자로 받는다.
- c 와 m이 같은 경우 : m, max(r,s) 반환

- c가 m보다 작은 경우 : c , s 반환

- c가 m보다 큰 경우 : m, r 반환

 

⑥ result 결과값으로 출력

 

6. 느낀점

누적합 문제로 푸는데 시간이 좀 걸렸다. 누적합을 미리 구하고 좌측그룹과 우측그룹의 차가 최소가 나오는 값을 구하는 문제로 인덱스를 이동하며 무게가 큰 그룹의 무게를 낮추는 식으로 문제를 해결했다.