[백준 20366] 같이 눈사람 만들래? (C++)

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

문제

---

20366번: 같이 눈사람 만들래?

언니! 똑...똑똑...똑똑! 같이 눈사람 만들래~? ♪

언니 엘자와 동생 안나에게는 N개의 눈덩이가 있다. 각 눈덩이 i (1 ≤ i ≤ N)의 지름은 Hi 이다. 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 두고 그 눈덩이보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만들 수 있다. 이때, 눈사람의 키는 두 눈덩이 지름의 합과 같다.

엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 각각 1개씩, 총 2개를 만들려고 한다. 두 자매는 두 눈사람의 키의 차이가 작을수록 두 눈사람의 사이가 좋을 것이라고 믿는다. 우리는 엘자와 안나가 가장 사이좋은 두 눈사람을 만들기 위해서 도와주려고 한다.

 

주어진 N개의 눈덩이를 이용하여 만들 수 있는 두 눈사람의 키 차이 중 최솟값을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N (4 ≤ N ≤ 600)이 주어진다.

둘째 줄에는 각 눈덩이 i (1 ≤ i ≤ N)의 지름을 의미하는 정수 Hi (1 ≤ Hi ≤ 109)가 공백으로 구분되어 주어진다.

 

출력

---

만들 수 있는 두 눈사람의 키 차이 중 최솟값을 나타내는 정수를 출력하라.

 

문제 풀이

---

투포인터 문제.

정렬후 2중 반복문으로 하나의 눈사람를 이루는 두 눈덩이(엘자의 눈사람)를 정한 후, 그 사이의 값을 가지는 눈덩이들 중 두 개의 합이 두 눈사람의 키 차이가 최소가 되도록 하는 눈덩이 두 개를 정한다. 처음에는 눈덩이 두 개를 i, j 사이 중 가장 작은 것(start)과 가장 큰 것(end)을 선정하여, 그 둘의 합이 엘자의 것보다 작다면 안나의 눈사람이 더 커질 수 있도록  start를 증가시킨다. 만약 엘자의 것보다 크다면 안나의 눈사람이 더 작아질 수 있도록 end를 감소시켜준다.

 

투포인터의 start와 end가 둘 다 처음에서부터 시작할 필요는 없다는 것을 알려주는 문제.

 

아래는 코드.

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

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

	int N;
	cin >> N;
	int* arr = new int[N];
	int start, end;
	int answer = 2000000000;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	for (int i = 0; i <= N - 4; i++)
	{
		for (int j = i + 3; j < N; j++)
		{
			start = i + 1;
			end = j - 1;
			int firstSnowman = arr[i] + arr[j];
			while (start < end)
			{
				int secondSnowman = arr[start] + arr[end];
				int diff = firstSnowman - secondSnowman;
				if (diff < 0)
				{
					end--;
				}
				else
				{
					start++;
				}
				answer = min(answer, abs(diff));
			}
		}
	}
	std::cout << answer << "\n";
	return 0;
}