[백준/BOJ] 백준 23032번 : 서프라이즈~

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

23032번: 서프라이즈~

 

1~n-1 지점을 모두 중간지점으로 해보면서, 해당 중간지점을 기준으로 왼쪽(left ~ 중간지점) 구역의 합과 오른쪽(중간지점+1 ~ right) 구역의 합의 차이를 작게 만들도록 left와 right를 움직여 가며 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
int weight[2005];
int psum[2005];

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		int input;
		cin >> input;
		weight[i] = input;
	}

	for (int i = 1; i <= n; i++) {
		psum[i] = psum[i - 1] + weight[i];
	}

	int min_diff = 987654321;
	int result = 0;

	//mid값을 정해서, mid값으로 부터 왼쪽[left~mid], 오른쪽[min+1,right] 으로 그룹을 나눈다
	for (int mid = 1; mid <= n - 1; mid++) {
		int left = mid;
		int right = mid + 1;

		while (left >= 1 && right <= n) {
			int left_sum = psum[mid] - psum[left - 1];
			int right_sum = psum[right] - psum[mid];

			//그룹간 차이가 더 작은 경우를 발견 했을때
			if (min_diff > abs(left_sum - right_sum)) {
				min_diff = abs(left_sum - right_sum);
				result = left_sum + right_sum;
			}

			//그룹간 차이가 같은 최솟값인데, 두 그룹의 합이 더 클때
			else if (min_diff == abs(left_sum - right_sum) && result < (left_sum + right_sum)) {
				min_diff = abs(left_sum - right_sum);
				result = left_sum + right_sum;
			}

			if (left_sum > right_sum) {
				right++; //오른쪽 그룹 늘리기
			}

			else {
				left--; //왼쪽 그룹 늘리기
			}
		}
	}

	cout << result;

	return 0;
}