[백준] 20366번 같이 눈사람 만들래? (C++)

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

 

 

이 문제는 N개의 눈덩이가 주어졌을때 4개의 눈덩이를 선택해서 2개 2개씩 눈사람을 만들었을때 그 크기의 차이를 가장 작게 만들어야 한다.

 

이때 눈덩이의 개수는 600개로 작다고 생각할 수 있지만 모든 탐색을 한다면 O(N^4)으로 상당히 큰 숫자가 나온다.

 

따라서 이를 최적화 하기 위해 값을 먼저 정렬을 한 이후 2개 2개를 선택하기 때문에 투포인터를 2개를 만들었다.

 

먼저 2중 for문으로 하나의 포인터를 잡고 0부터 N-1까지 하나의 포인터를 잡아서 탐색하였다.

 

이렇게 되면 시간복잡도가 O(N^3)으로 2억정도 나온다.

 

 

정답코드

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

const int INF = 2e9 + 7;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N;
int arr[601];
int answer = INF;

void solve() {
    sort(arr, arr+N);

    for(int i = 0; i < N-1; i++) {
        for(int j = i+1; j < N; j++) {
            int snow1 = arr[i] + arr[j];

            int lo = 0;
            int ri = N-1;

            while(lo < ri) {
                if(j == lo || i == lo) {
                    lo++;
                    continue;
                }

                if(j == ri || i == ri) {
                    ri--;
                    continue;
                }

                int snow2 = arr[lo] + arr[ri];
                answer = min(answer, abs(snow2 - snow1));

                if(snow1 < snow2) {
                    ri--;
                }
                else if(snow1 > snow2) {
                    lo++;
                }
                else {
                    answer = 0;
                    break;
                }
            }
        }
    }

    cout << answer;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        cin >> arr[i];
    }
}

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

    input();
    solve();
}

 

먼저 하나씩 코드를 살펴보자

 

void solve() {
    sort(arr, arr+N);

    for(int i = 0; i < N-1; i++) {
        for(int j = i+1; j < N; j++) {
            int snow1 = arr[i] + arr[j];

            int lo = 0;
            int ri = N-1;

            while(lo < ri) {
                if(j == lo || i == lo) {
                    lo++;
                    continue;
                }

                if(j == ri || i == ri) {
                    ri--;
                    continue;
                }

                int snow2 = arr[lo] + arr[ri];
                answer = min(answer, abs(snow2 - snow1));

                if(snow1 < snow2) {
                    ri--;
                }
                else if(snow1 > snow2) {
                    lo++;
                }
                else {
                    answer = 0;
                    break;
                }
            }
        }
    }

    cout << answer;
}

 

가장 핵심인 2개의 포인터를 사용하는 부분이다 먼저 2중 for문으로 i, j를 잡는다

이는 하나의 포인터이며

또 다른 포인터는 0과 N-1로 포인터를 잡는다.

이후 left right 포인터가 i, j 포인터와 겹칠경우 left는 왼쪽 포인터이기 때문에 left를 늘려주고 right는 감소시켜준다.

 

이후 차이값을 갱신시키며 이후 두개의 눈덩이의 크기가 비슷해야지 차이가 거의 안나기 때문에 i, j(고정된 포인터)의 눈사람의 크기가 더 큰 경우 left를 증가시켜 두번째 눈사람의 크기를 증가시키고 아닐 경우 감소시켜 눈사람의 크기를 줄어들게 한다.

정답코드

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

const int INF = 1e9;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N;
int arr[601];
vector<tuple<int, int, int>> v;
int answer = INF;

void solve() {
    for(int i = 0; i < N; i++) {
        for(int j = i + 1; j < N; j++) {
            v.push_back({arr[i] + arr[j], i, j});
        }
    }

    sort(v.begin(), v.end());

    for(int i = 0; i < v.size(); i++) {
        for(int j = i + 1; j < v.size(); j++) {
            int idx1 = get<1>(v[i]);
            int idx2 = get<2>(v[i]);

            int idx3 = get<1>(v[j]);
            int idx4 = get<2>(v[j]);

            if((idx1 != idx3) && (idx1 != idx4) && (idx2 != idx3) && (idx2 != idx4)) {
                int diff = get<0>(v[j]) - get<0>(v[i]);
                answer = min(answer, diff);
            }
            else break;
        }
    }

    cout << answer;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        cin >> arr[i];
    }
}

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

    input();
    solve();
}

 

또 다른 풀이 방법으로 나올 수 있는 눈덩이의 크기를 만들고 만든 눈덩이의 인덱스도 넣어준다.

 

이후 인접한 눈덩이 끼리 비교하고 해당하는 4개의 인덱스가 다 다를 경우 최소값을 업데이트하여 출력한다.