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

leeeha·2022년 7월 6일

백준

목록 보기

43/185

문제

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

입력

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

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

출력

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

예제

풀이

조합, 그리디 (시간 초과)

N개 중에 4개를 선택하는 경우의 수를 모두 구하고 (N은 최대 600)

다시 4개 중에 2개를 선택하는 경우의 수 중에

두 눈사람의 높이 차이가 최소가 되는 것을 구한다.

4개 중에 2개를 선택할 때는 '차이가 최소'여야 하므로 인덱스를 (0, 3) (1, 2) 또는 (0, 2) (1, 3) 이런 식으로 두 가지 경우만 선택하였다. (그리디하게 높이가 작고 큰 것끼리 묶일 수 있도록)

그런데, N개 중에 4개를 선택하는 경우의 수는

nC4 = n * (n-1) * (n-2) * (n-3) / 4! 이기 때문에

시간복잡도가 O(N^4)이 되어서 시간초과가 뜰 수밖에 없다.

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 601;
int N;
vector<int> arr;
bool selected[MAX];
int temp[MAX];
int ans = 2e9;

void input(){
	cin >> N;

	for(int i = 0; i < N; i++){
		int x;
		cin >> x;
		arr.push_back(x);
	}

	sort(arr.begin(), arr.end());
}

// 눈사람 높이 차이의 최솟값 구하기 
void updateMinGap(){
	ll s1 = temp[0] + temp[3];
	ll s2 = temp[1] + temp[2];
	if(abs(s1 - s2) < ans){
		ans = abs(s1 - s2);
	}

	ll s3 = temp[0] + temp[2];
	ll s4 = temp[1] + temp[3];
	if(abs(s3 - s4) < ans){
		ans = abs(s3 - s4);
	}
}

// idx: 탐색을 시작할 인덱스 
// cnt: 현재까지 뽑은 개수 
// N개 중에 4개 선택
void dfs(int idx, int cnt){
	if(cnt == 4){
		updateMinGap();
		return;
	}

	for(int i = idx; i < N; i++){
		if(!selected[i]){
			selected[i] = true;
			temp[cnt] = arr[i];

			// idx가 아니라 i를 넣어줘야 한다. 
			dfs(i + 1, cnt + 1); 
			
			selected[i] = false;
		}
	}
}

void solution(){
	dfs(0, 0);
	cout << ans;
}

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

	input(); 
	solution();

	return 0;
}

더 효율적인 방법을 생각해야 한다!!

투 포인터

우선, 배열을 오름차순으로 정렬한 후에

첫번째 합을 구하기 위한 투포인터 i, j를 세팅한다.

그리고 그 사이에 있는 숫자들로 두번째 합을 구하기 위한 투포인터 l, r를 세팅한다.

i l r j -> (i, j) (l, r)

배열을 정렬했기 때문에 가능한 한 '높이가 작고 큰 것끼리' 최대한 같이 묶으면

두 눈사람의 높이 차이는 최소가 될 것이다.

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 601;
int N;
vector<int> arr;
int ans = 2e9;

void input(){
	cin >> N; 

	for(int i = 0; i < N; i++){
		int x; 
		cin >> x; 
		arr.push_back(x);
	}
}

void solution(){
	sort(arr.begin(), arr.end());
	
	for(int i = 0; i < N - 3; i++){
		for(int j = i + 3; j < N; j++){
			int l = i + 1, r = j - 1;

			while(l < r){
				int h1 = arr[i] + arr[j];
				int h2 = arr[l] + arr[r];

				ans = min(ans, abs(h1 - h2));

				if(h1 > h2){
					l++;
				}else{
					r--;
				}
			}
		}
	}

	cout << ans; 
}

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

	input(); 
	solution();

	return 0;
}