[BOJ] 16287. Parcel

16287번: Parcel

요약하자면, 주어진 배열 A 안의 임의의 4개의 원소들의 합이 W가 되는 경우가 있는지 여부를 출력하는 문제이다.

 

처음 생각났던 풀이는 앞의 세 원소는 하나씩 고르고 마지막 원소는 lower_bound로 찾기였다. 당연히 세 원소 고르는 것만 O(N^3)이고 N ≤ 5,000인데 될리가 없다.

시간복잡도 O(N^2) 안에 풀어야 하기 때문에 원소들을 두 개씩 묶는다는 아이디어까지는 쉽게 떠올릴 수 있었다.

원소 두 개씩 쌍을 만들어 pair에 넣고 그 합을 기준으로 정렬한 후 lower_bound로 합을 찾아서 그 pair 안에 있는 값들이 겹치지 않는지 확인하기.. 인데 각 합을 구성할 수 있는 pair도 여러개 있고, 원소가 안 겹치는지 체크하기도 귀찮았다.

 

그런데 스터디원이 블로그에서 찾았다며 풀이를 알려주어서 그 풀이를 바탕으로 코드를 짤 수 있었다.

 

#include <bits/stdc++.h>

using namespace std;

int w, n;
vector<int> a;
bool b[800001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> w >> n;
    for (int i = 0; i < n; i++)
    {
        int q;
        cin >> q;
        a.push_back(q);
    }
    sort(a.begin(), a.end());
    bool flag = false;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[i] + a[j] < w && b[w - a[i] - a[j]])
                flag = true;
        }
        for (int j = 0; j < i; j++)
        {
            if (a[i] + a[j] < w)
                b[a[i] + a[j]] = true;
        }
    }
    cout << (flag ? "YES" : "NO");
    return 0;
}

 

일단 모든 원소들을 정렬하고 (안 해도 됨), bool 배열 b[i]에는 i번째 원소보다 앞에 있는 (작은) 원소들로 i를 만들 수 있는지의 여부이다.

사실 이런 풀이들은 정말 어떻게 생각하는지 모르겠다. 스터디원들도 다들 대체 이런 풀이는 어떻게 생각하는거냐며 울었다...

푸는 모든 문제들을 포스팅하기는 어렵겠지만 스터디에 가져가는 매주 2개의 문제들은 혼자 고민해서는 못 풀었던 문제들이기 때문에 풀이를 정리해서 업로드하는 게 좋겠다는 생각이 들었다.