백준 16287번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	512MB

사진을 클릭하면 문제로 이동합니다.

---

풀이

 푸는데 6일 이상 걸린 문제이다. 물론 이거만 고민하지 않고, 조금 고민하다가 다른 문제나 풀어야지 하면서 도망간 것도 있지만.... 아무튼 오랜 시간이 걸린 문제이다.

 

 이 문제는 이전에 풀었던 7453번 합이 0인 네 정수(https://codejin.tistory.com/298)와 비슷한 느낌의 문제이다. 초반 풀이는 비슷한데, 후반의 처리 방식이 다른 문제이다.

백준 7453번 C++ 풀이

 

두개의 쌍을 찾는건 편하지만, 네개의 쌍을 찾는건 굉장히 어렵다. 물론 4중 반복문을 돌면 될일이겠지만, 그걸 허락할 PS가 아니잖나. 그렇기에 두개의 쌍을 먼저 구한후, 구한 쌍들을 다시 쌍을 짓는 방식을 이용한다. 이 방식은 7453번에서도 사용했던 풀이이다. 저번 문제에서는 이 방식을 사용하면 편했지만, 이번 문제는 그렇지 않다. 7453번에서는 4개의 배열에서 원소를 하나씩 집으면 되기에, 중복으로 고른다거나 하는 걱정을 할 필요가 없었지만, 이번에는 다르다. 하나의 배열에서 중복되지 않도록 네개의 원소를 선택해야한다. 두개의 쌍의 합을 합칠때는 이중 반복문에서 인덱스를 조절해가면 되지만, 만들어진 쌍들을 다시 쌍을 지을때 중복되는 원소를 사용할 수도 있다. 이에 대한 해결을 해야했다.

 

 처음에는 어떤 무게를 만드는데 필요한 조합을 모두 검사했다. 솔직히 하나의 조합을 만드는데 그렇게 많은 원소가 존재하지 않을 것이라 생각하고 이중반복문을 한번 더돌렸다. 그래서 당연하게 TLE를 받았다.

코드-TLE1

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;

int w, n;
vector<int> parcel;

void input() {
    cin >> w >> n;
    parcel.resize(n);
    for(int& p : parcel) cin >> p;
    sort(ALL(parcel));
}

void sol() {
    vector<vector<pair<int,int>>> ab(799995);

    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            ab[parcel[i] + parcel[j]].emplace_back(parcel[i], parcel[j]);
        }
    }

    for(int i = 3; i <= w / 2; i++) {
        if (ab[w - i].size() != 0 && ab[i].size() != 0) {
            for(auto& [a, b] : ab[i]) {
                for(auto& [c, d] : ab[w - i]) {
                    if (a != c && a != d && b != c && b != d) {
                        cout << "YES";
                        return;
                    }
                }
            }
        }
    }
    cout << "NO";
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    input();
    sol();
}

 

 두개의 쌍을 먼저 찾는건 해야하는 작업이고 코드이기에, 뒤에 조합의 중복을 검사하는 부분이 WA의 주 원인일 것이다. 저 부분을 개선해야했다. 다양한 방법을 시도했다. 이분탐색을 활용하기도 해봤었다. 임의의 무게 w'를 만드는데 (i, j) 인덱스의 원소를 사용했다면, 구간 [j + 1, n) 의 구간에서 w - w'를 만들 수 있는지 확인하면되기 때문이다. [i + 1, j - 1] 구간을 보지 않는 이유는, 만약 이 중간의 인덱스 k의 원소를 사용했다면, 이전 또는 이후에 w''를 만드는 (i, k)를 볼 것이고, 같은 행위를 반복할 것이기 때문이다. 문제는 결국 [j + 1, n) 구간의 원소를 하나씩 보면서 이분탐색을 해야했기에, TLE를 받았다.

코드-TLE2

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;

int w, n;
vector<int> parcel;

void input() {
    cin >> w >> n;
    parcel.resize(n);
    for(int& p : parcel) cin >> p;
    sort(ALL(parcel));
}

void sol() {
    vector<vector<pair<int,int>>> ab(799995);

    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            ab[parcel[i] + parcel[j]].emplace_back(i, j);
        }
    }

    for(int w_ab = 3; w_ab <= w / 2; w_ab++) {
        if (ab[w_ab].size() == 0) continue;

        // for(auto& [_, r] : ab[w_ab]) {
        int r = (*(ab[w_ab].end() - 1)).second;
        for(auto st = parcel.begin() + r + 1; st != parcel.end(); ++st) {
            int target = w - w_ab - *st;
            if (*lower_bound(st, parcel.end(), target) == target) {
                cout << "YES";
                return;
            }
        }
    }

    cout << "NO";
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    input();
    sol();
}

 

개선할 방법을 계속해서 찾다가, 문득 그런 생각이 들었다. 굳이 모든 조합을 살펴봐야하는지가 의문이었다. 사실 지금까지의 문제는 모든 조합중에서 중복이 없는지를 살펴보려고 했기 때문에 생기는 문제였다. 생각을 해보았다. 다음과 같은 예제가 있다고 해보자. 원래는 순서가 뒤죽박죽이었지만, 보기 편하게 정렬했다고 하자.

 

1 3 5 7 9 11 13 18 132 9812

 

여기서 14를 만드는 쌍은 무엇일까? (1, 13), (3, 11), (5, 9)일 것이다. 이들을 인덱스로 바꿔보자. (0, 6), (1, 5), (2, 4)가 된다. 쌍을 찾으면 찾을수록, 더 큰값의 인덱스 (i, j 꼴일때 j 값)가 점점 줄어드는 것을 볼 수 있다. j가 작아질 수록 조합의 자유는 늘어날 것이다. 왜냐하면 위에서 말했듯이 (i, j) 를 찾았으면, 구간 [j+1, n)에서 나머지 조합을 찾으면 되기 때문에, j가 작아질 수록 조합하기 편해질 것이다. 만약 [j + 1, n) 구간에서 다른 나머지 조합을 찾았다면, 이는 답이 될 것이다. 

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;

int w, n;
vector<int> parcel;

void input() {
    cin >> w >> n;
    parcel.resize(n);
    for(int& p : parcel) cin >> p;
    sort(ALL(parcel));
}

void sol() {
    vector<pair<int,int>> ab(799995, {-1, -1});

    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            ab[parcel[i] + parcel[j]] = {i, j};
        }
    }

    for(int w_ab = 3; w_ab <= w / 2; w_ab++) {
        auto& [a, b] = ab[w_ab];
        auto& [c, d] = ab[w - w_ab];
        if (a == -1 || b == -1 || c == -1 || d == -1) continue;

        if (a != c && a != d && b != c && b != d) {
            cout << "YES";
            return;
        }
    }
    cout << "NO";
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    input();
    sol();
}