BOJ - 16287번 Parcel

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

16287번: Parcel

ICPC 서울 인터넷 예선 2018에 나온 문제입니다.

 

주어지는 N개의 수 중에서 정확히 4개를 뽑아 내어 합이 w가 되게 만들 수 있는지를 묻는 문제입니다.

 

naive한 생각으로는 N개중 4개를 뽑아 w를 만드는지 확인하는 방법이 존재합니다. 하지만 이 해법은 $_NC_4$로 N이 5000이나 되기 때문에 불가능합니다.

 

좀 더 생각해 보면 존재만을 확인하면 되기 때문에 임의의 두 수의 합을 더한 결과와 또 다른 임의의 두 수를 더한 결과가 w가 되는지만 알 수 있으면 되는 문제입니다.

 

이때 중요한 점은 w가 최대 약 80만이기 때문에 두 수의 합의 존재를 배열로 만들어 관리가 가능했고, 이 덕에 반복문을 안겹치게 잘 구성한다면 $O(N^2)$에 본 문제를 풀 수 있었습니다.

 

iterator로 사용할 k를 N - 1부터 시작하여 k와 0 ~ k - 1번째 값들의 합이 P라 했을때 w - P가 이전에 이미 나왔는지 확인 후, 있다면 YES를 출력 후 종료하고 그런 값이 존재하지 않는다면 k와 k + 1 ~ N - 1 번째 수 와의 합을 존재한다고 체크해 줍니다.

 

이를 반복하면 똑같은 결과를 두 번 계산하지 않고 $O(N^2)$에 해결 가능합니다.

#include <iostream>
#include <vector>
using namespace std;
int N, w;
vector<int> a;
bool twosum[800005];

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> w >> N;
    a.resize(N);
    for (int i = 0; i < N; i++)
        cin >> a[i];
    for (int i = N - 1; i >= 0; --i)
    {
        for (int j = i - 1; j >= 0; --j)
        {
            if (w - a[i] - a[j] >= 0 && twosum[w - a[i] - a[j]])
            {
                cout << "YES\n";
                return 0;
            }
        }
        for (int j = i + 1; j < N; j++)
            twosum[a[i] + a[j]] = true;
    }
    cout << "NO\n";
    return 0;
}