[백준/C++] #20366 같이 눈사람 만들래? (Two Pointer)

문제

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

그래도.. 시간 줄이긴 줄였네..ㅋㅋ

구상

N개의 눈덩이를 가지고, 4개의 눈덩이를 골라, 2개의 눈사람을 만드는데, 두 눈사람의 높이의 차가 최소가 되도록 하여 최소인 높이 차를 출력하는 문제였다. 지금보면 진짜 바보같지만, 처음에는 진짜 내가 이걸 1초만에 생각해낸게 신기할 정도로 쉬워보이는 풀이 (결과적으로 틀린 풀이) 를 생각해냈다. 

 

무엇이었냐 하면, 눈사람의 지름이 a, b, c, d라 하면, (a+b) - (c+d)의 값이 가장 작으면 되니까, (a-c)-(d-b)의 최소값을 구하면 되겠다 생각해서 눈사람의 지름 오름차순으로 정렬하고, 인접한 배열의 값끼리의 차를 구한 배열을 만들어서, 그걸 또 정렬해서(인덱스 값과 함께 pair로. 인접한것 고르면 안되니까), 해당 배열에서 값들간의 최소를 구하려했다. 허헣 뭔가 말은 돼보이는데, 사실 (a-c), (d-b)값 각각이 최소가 될 필요가 없다......ㅋㅋ 난 바보야..

 

그래서 머리 식히고 생각해낸게 정말 어이없게도 정답이 된 풀이인데, 그냥 2개 눈덩이 고르고, 해당 눈덩이와 지름의 합이 가장 유사한 눈덩이 두개를 찾는 것이었다. 사실 시간도 널널했고, 눈덩이의 개수인 N도 최댓값이 600으로 크지 않았다. 눈덩이 크기 정렬하고(O(NlogN), 2중 for문으로 눈덩이 두개 고르고(O(N^2)), two pointer로 나머지 2개 찾으면(O(N)) 결국 O(NlogN) + O(N^3) 가 되었다. O(N^3)을 계산해보면 2.16억이 되어 최악의 경우, 백준 기준으로 약 2초 정도가 걸린다. (백준: 1초에 약 1억번 연산)  그래서 조금만 더 효율적으로 수정하면, 되겠다 싶어 해당 로직으로 코드를 작성했는데 성공!

 

느낀점

영진님께서 소프트콘에서 말씀하신 것처럼 처음에는 일단 블루트포스로 접근하고, 시간복잡도를 따져가며 적용할 수 있는 알고리즘을 찾자. 제발 처음부터 효율적으로 하겠다고 나만의 풀이를 만들어내지 말자. 언제나 내가 인지하지 못한 반례가 존재할 수 있다는 사실을 잊지 말자. 그리고, 나만의 테케를 많이 만들어보자!!

https://www.youtube.com/watch?v=dXr13v5im6Y

 

알고리즘

정렬 후 두개의 포인터로 합이 특정 값과 가장 유사한 두개의 값을 찾는 거니까 two pointer를 이용했다!

 

오늘 상신오빠한테 투포인터랑 슬라이딩윈도우 차이 물었다가 예시로 합 구할 때 투포인터 쓴다고 들었었는데, 이렇게 바로 쓰이는거 보니 신기하당 ㅋㅋ 

 

풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define MAX 1000000001;
#define endl "\n"
using namespace std;
/*
20366 같이 눈사람 만들래?
*/
int N; // 4~600
vector<int> H;
int res = MAX;

void solution() {
    sort(H.begin(), H.end()); // 오름차순
    // 2중 for문으로 2개 고르기 -> 360,000
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            int sum = H[i] + H[j];

            // two pointer로 2개 찾기 -> 216,000,000
            int left = i+1; int right = N - 1;

            while (left < right) {

                if (right == j || right == i) {
                    right--;
                    continue;
                }
                if (left == j || left == i) {
                    left++;
                    continue;
                }

                int sum2 = H[left] + H[right];
                res = min(res, abs(sum - sum2));

                // 합이 작으면 + 갱신
                if (sum2 < sum){
                    left++;
                }

                // 합이 크면 + 갱신
                else if (sum2 > sum) {
                    right--;
                }

                // 합이 같으면
                else {
                    res = 0; 
                    break;
                }

            }
        }
    }
    cout << res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> N;
    H.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> H[i];
    }

    // 로직
    solution();

    return 0;

}