[백준 알고리즘] 20366번: 같이 눈사람 만들래?
April 10, 2021
https://www.acmicpc.net/problem/20366
문제
문제
언니 엘자와 동생 안나에게는 N개의 눈덩이가 있다. 각 눈덩이 i (1 ≤ i ≤ N)의 지름은 Hi 이다. 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 두고 그 눈덩이보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만들 수 있다. 이때, 눈사람의 키는 두 눈덩이 지름의 합과 같다.
엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 각각 1개씩, 총 2개를 만들려고 한다. 두 자매는 두 눈사람의 키의 차이가 작을수록 두 눈사람의 사이가 좋을 것이라고 믿는다. 우리는 엘자와 안나가 가장 사이좋은 두 눈사람을 만들기 위해서 도와주려고 한다.
주어진 N개의 눈덩이를 이용하여 만들 수 있는 두 눈사람의 키 차이 중 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (4 ≤ N ≤ 600)이 주어진다.
둘째 줄에는 각 눈덩이 i (1 ≤ i ≤ N)의 지름을 의미하는 정수 Hi (1 ≤ Hi ≤ 109)가 공백으로 구분되어 주어진다.
출력
만들 수 있는 두 눈사람의 키 차이 중 최솟값을 나타내는 정수를 출력하라.
풀이
첫번째 눈사람에 대해서는 모든 경우의 수를 다 시도하고, 두번째 눈사람에 대해서 투포인터를 적용하여 N^3 으로 풀었다. 먼저 입력받은 눈덩이들의 값을 오름차순으로 정렬한다. 그리고 투 포인터의 위치를 start는 0, end 는 N-1로 배열의 마지막을 가르키게 한다. 핵심은 두 눈사람의 차를 항상 첫번째 눈사람을 기준으로 하는 것이다. 두번째 눈사람의 높이가 첫번째 눈사람보다 작으면서 가장 큰 값을 찾아내면 된다. 이제 2중 for 를 돌면서 첫번째 눈사람을 조합하고 남은 눈덩이들로 눈사람을 만들어본다. 이때 두번째 눈사람의 높이가 첫번째보다 작다면, start 값을 증가시켜서 눈 사람의 높이를 증가시켜본다. 만약 두번째 눈사람의 높이가 첫번째보다 크다면, 높이를 줄여줘야하므로 end 값을 감소시켜서 눈덩이를 작게 만든다.
두번째 눈사람을 만들때마다 첫번째 눈사람과의 차를 구해서 가장작은 값을 계속 업데이트하면 답을 얻을 수 있다.
코드
#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int N;
cin >> N;
int snows[601];
for (int i = 0; i < N; i++) {
cin >> snows[i];
}
sort(snows, snows + N);
int minDiff = INT_MAX;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
int start = 0, end = N - 1;
while (true) {
if (start == i) {
start++;
}
if (start == j) {
start++;
}
if (end == j) {
end--;
}
if (end == i) {
end--;
}
if (start >= end) break;
int firstPair = snows[i] + snows[j];
int secondPair = snows[start] + snows[end];
int diff = abs(firstPair - secondPair);
minDiff = min(minDiff, diff);
if (firstPair > secondPair) {
start++;
}
else {
end--;
}
}
}
}
cout << minDiff;
}
