[백준OJ] 20366번 같이 눈사람 만들래?

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

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

---

 

 

풀이

먼저 모든 눈사람의 크기를 구해준다. 2중for문을 이용하여 모든 조합을 완성 시킬 수 있다.

그런 뒤, 두 눈사람의 크기차이의 최솟값을 찾으면 되는것이기때문에 눈사람의 크기순으로 정렬을 한 뒤, 자신의 바로 뒤의 눈사람과 비교를 해서 값을 갱신시켜주면 된다. 이때 서로다른 4개의 눈덩이를 골라야하므로, 눈사람 2개를 골랐을때, 중복된 눈덩이가 있는지 확인 후, 없으면 최솟값을 갱신하면 된다.

 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define MAX	2000000001
using namespace std;
typedef pair<int, int> pii;
vector<pair<pii,int>> sum_v;
int n;
vector<int> arr;

bool compare(pair<pii, int> a, pair<pii, int> b) {
	return a.second < b.second;
}

int main() {
	cin >> n;
	arr.resize(n);
	for (int i = 0; i < n; i++) cin >> arr[i];

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			sum_v.push_back({ {i,j},arr[i] + arr[j] });
		}
	}
	sort(sum_v.begin(), sum_v.end(), compare);
	int ret = MAX;
	for (int i = 0; i < sum_v.size()-1; i++) {
		for (int j = i + 1; j < sum_v.size(); j++) {
			int i1 = sum_v[i].first.first;
			int j1 = sum_v[i].first.second;
			int c1 = sum_v[i].second;

			int i2 = sum_v[j].first.first;
			int j2 = sum_v[j].first.second;
			int c2 = sum_v[j].second;

			if (i1 != i2 && i1 != j2 && j1 != i2 && j1 != j2) {
				ret = min(ret, abs(c1 - c2));
				break;
			}
		}
	}
	cout << ret;

	return 0;
}