백준 20366 C++

백준 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개, 2개를 골라서 그 2개들의 합들이 차이가 최소가 되게 하는 법이다. 단순무식한 방법으로는 4중 for문으로 모든 케이스에 대한 조사를 하는 방법이 있겠지만. 그러면 O(N^4)로 600^4 = 129,600,000,000

1초에 1억번 기준 1296초라서 자연스럽게 시간초과가 난다. 따라서 이건, 다른 방법으로 풀어야 한다. 우리가 알 수 있는 건, 최소값, 최대값… 즉 차이를 구하는 거고, 이는 숫자의 범위? 와도 관련이 있다.

따라서, 이런 문제를 많이 봤다면 자연스레 알 수 있듯이 투포인터 문제다. 그런데 문제는 2번, 2번… 즉 투 포인터를 2번 해야하는 것 같은 문제인데. 그렇지 않아도 풀 수 있다!

N이 600이기에, 2중 FOR문으로 첫 번째 눈사람을 만들어 준 후에, 거기서 최솟값을 구하는 방식으로 투 포인터를 구현해주면 된다.

일단 투 포인터를 구해야하기 때문에, 처음에 정렬해준다. 그리고 2중 for문으로 첫 번째 눈사람을 만들어준다.

여기서 우리는 첫 번째 눈사람에서 쓰인 눈뭉치를 피해서 투포인터를 해준다.

left = 0, right = N - 1로 범위를 잡아준 후에 일반 투 포인터와 비슷하게 while(left < right)로 범위 지정을 해준다.

또 내부에서 기존에 쓰인 눈뭉치를 피하기 위해. if(left == y || left == x){ left++; continue; } if(right == y || right == x){ right–; continue; } 로 피해준다.

그리고 그 두 눈뭉치의 합을 구해준다. 그리고 첫 번째 눈뭉치와 두 번째 눈 뭉치를 빼준다.

sum1 - sum2 이런 방식으로. 만약 값이 -이면, sum2를 줄여야 하므로 right–해주고, +이면 sum2를 늘려야 하므로 left++해주는 방식이다. 또, 포인터들을 움직일 때, 우리가 결국 구해야하는 건 ‘최솟값’이기에 dif = min(dif, abs(sum1 - sum2));이런 방식으로 해주면 되는. 그리 어렵진 않은 문제다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>


using namespace std;
int N;
vector<int> v1;

int dif = 1987654321;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	v1.resize(N);
	for (int y = 0; y < N; ++y) {
		cin >> v1[y];
	}
	sort(v1.begin(), v1.end());


	for (int y = 0; y < N - 1; ++y) {
		for (int x = y + 1; x < N; ++x) {
			int sum = v1[y] + v1[x];

			int left = 0, right = N - 1;

			while (left < right) {
				if (left == y || left == x) {
					left++;
					continue;
				}
				if (right == y || right == x) {
					right--;
					continue;
				}
				int sum2 = v1[left] + v1[right];
				int gap = sum - sum2;

				if (!gap) {
					cout << 0;
					return 0;
				}
				else if (gap < 0) {
					right--;
					dif = min(dif, abs(gap));
				}
				else {
					left++;
					dif = min(dif, abs(gap));
				}
			}
		}
	}

	cout << dif;
	return 0;
}

BOJ 카테고리 내 다른 글 보러가기