[백준/BOJ] 백준 20366번 : 같이 눈사람 만들래?

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

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

눈을 크기 순으로 정렬하고, 하나의 눈사람을 만들 눈 i, j를 고르는 상황을 고려해서 해당 눈 i와 j사이의 다른 눈사람을 만들 눈 두 개를 left, right로 해서 중간에서 만나는 투 포인터를 이용해서 문제를 해결했다.

 

코드

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

int n;
vector<int> snow;
int result = 1000000001;

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

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		snow.push_back(input);
	}

	sort(snow.begin(), snow.end());

	//눈사람 하나를 만들 눈 i,j를 고른다
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 3; j < n; j++)
		{
			int snow_man1 = snow[i] + snow[j];

			//눈 i와 j사이의 다른 눈사람을 만들 눈 left,right를 가운데서 만나는 투포인터를 이용해 구한다
			int left = i + 1;
			int right = j - 1;
			while (left < right)
			{
				int snow_man2 = snow[left] + snow[right];

				if (snow_man1 - snow_man2 == 0)
				{
					result = 0;
					break;
				}

				//snow_man2의 크기를 더 늘려야 될때 (left를 오른쪽으로)
				else if (snow_man1 - snow_man2 > 0)
				{
					result = min(result, abs(snow_man1 - snow_man2));
					left++;
				}

				//snow_man2의 크기를 더 줄여야 될때 (right를 왼쪽으로)
				else if (snow_man1 - snow_man2 < 0)
				{
					result = min(result, abs(snow_man1 - snow_man2));
					right--;
				}

			}
			if (result == 0)
				break;
		}

		if (result == 0)
			break;
	}

	cout << result;

	return 0;
}