백준 23032: 서프라이즈~

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

 

서프라이즈! 다음과 같은 조건을 만족하는 학생들에게 스테이크를 드려요!

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이 2000 이하이므로 시간복잡도가 O(N^2)정도까지만 가능하다.

 

두 그룹을 첫 그룹을 1~3, 두 번째 그룹을 4~5 이런식으로 나누는 방식인데, 첫 그룹에서 학번이 제일 작은 사람을 x, 학번이 제일 큰 사람을 i, 두 번째 그룹에서 학번이 제일 큰 사람을 y라고 두면 이 경우 x=1, i=3, y=5가 되는 셈이다. 이런 식으로 1부터 N까지 자연수 중 임의의 자연수 x,i,y를 고르면 두 그룹이 결정되는 것이고 그 경우의 수는 N에서 3개를 고르는 조합 

과 같다. (즉, N^3에 비례하는데 이러면 모든 경우를 다 확인하려면 시간복잡도가 O(N^3)가 되어 시간 초과가 날 것이다.)

 

투 포인터 방식으로 해결하겠다. 

 

일단 i를 먼저 정해준다. 그리고 초기 x를 1로, 초기 y를 N으로 설정한다. 우리의 목표는 첫 그룹의 스테이크 양의 합과 두 번째 그룹의 스테이크 양의 합의 차를 최소로 만드는 것이다.

 

만약 왼쪽 그룹의 스테이크가 더 많다면 오른쪽 그룹에서 스테이크를 덜어가면 그건 스테이크 양의 차를 키울 뿐이다. 그래서 초기 상태보다 답에서 더 멀어진다. 그러므로 우리는 절대 이런 짓을 하지 않을 것이다. 왼쪽 그룹에서 스테이크를 덜어가겠다. 그러다가 오른쪽 그룹의 스테이크가 더 커진다면 오른쪽 그룹의 스테이크를 덜어가면 된다. 이런 식으로 모든 경우의 수를 확인해보면 그 중에 답을 찾을 수 있다. x를 점점 늘리면 왼쪽 그룹의 스테이크를 덜어가는 것이고 y를 점점 줄이면 오른쪽 그룹의 스테이크를 점점 덜어가는 것이다.

 

시간복잡도는 i를 정하는 데 N, 그리고 x는 커지기만 하고 y는 작아지기만 하므로 x와 y를 정하는 시간복잡도도 N에 비례해, 총 시간복잡도는 O(N^2)이다.

 

다음은 소스코드이다. C++로 작성했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>


using namespace std;
typedef long long ll;


int main()
{
    ll n;
    
    cin>>n;
    
    ll b[2200];
    
    ll h[2200];
    h[0]=0;
    ll ans=2100000000;
    ll steak=0;
    for(ll i=0;i<n;i++)
    {
        cin>>b[i+1];
        h[i+1]=h[i]+b[i+1];
    }
    for(ll i=1;i<n;i++)
    {
        ll x=1,y=n;
        while(1)
        {
            ll hl=h[i]-h[x-1];//왼쪽 그룹 스테이크 합
            ll hr=h[y]-h[i];//오른쪽 그룹 스테이크 합
            ll j=abs(hl-hr);//스테이크 양의 차
            if(j<ans)
            {
                ans=j;
                steak=hr+hl;
            }
            else if(j==ans)
            {
                steak=steak>hl+hr?steak:hl+hr;
            }
            if(hl>hr)
            {
                x++;
                if(x>i)
                {
                    break;
                }
            }
            else
            {
                y--;
                if(y<=i)
                {
                    break;
                }
            }
        }
        
    }
    
    cout<<steak;
    
    return 0;
}