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;
}
두 쌍의 투포인터가 1차원 배열을 순회한다는 점에서 시간복잡도는 O(N^2)이라고 볼 수 있다.
+ 배열 정렬은 O(NlogN)