[백준] 23032번 : 서프라이즈~ (C++)

23032번 : 서프라이즈~

---

문제)

 

쿠기는 가톨릭대학교 컴퓨터정보공학부 학부장이다. 곧 다가오는 시험 기간에 학생들에게 힘을 주고자 간식 행사에 안심 스테이크를 주려고 한다.

 

컴퓨터정보공학부에는 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번 학생이 이벤트 당첨자다.

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

 

쿠기를 도와 당첨자들의 스테이크 무게 합을 구하는 프로그램을 작성하시오.

 

 

입력 :

첫째 줄에 정수 N(2 ≤ N ≤ 2,000)이 주어진다.

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

 

 

 

출력 :

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

 

 

 

 

 

 

 

풀이)

// 23032. 서프라이즈~
#include <iostream>
#include <vector>
#include <limits.h>
 
using namespace std;
 
int n;
vector<int> vec;
vector<int> prefix;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    vec.resize(n + 1);
    prefix.resize(n + 1);
 
    int temp;
    for (int i = 1; i < n + 1; i++)
    {
        cin >> temp;
        vec[i] = temp;
        prefix[i] = prefix[i - 1] + temp;
    }
 
    int ans = INT_MAX;
    int answer = 0;
 
     for (int i = 1; i <= n; i++)
    {
        int s = i;
        int e = i + 1;
 
        while (s > 0 && e <= n)
        {
            int left = prefix[i] - prefix[s - 1];
            int right = prefix[e] - prefix[i];
 
            if (ans > abs(right - left))
            {
                ans = min(ans, abs(right - left));
                answer = prefix[e] - prefix[s - 1];
            }
            else if (ans == abs(right - left))
            {
                answer = max(answer, prefix[e] - prefix[s - 1]);
            }
 
            if (left >= right) e++;
            else s--;
        }
    }
 
    cout << answer;
 
    return 0;
}

---

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

23032번: 서프라이즈~