[BOJ] 백준 16287 - Parcel

문제 링크

www.acmicpc.net/problem/16287

16287번: Parcel

 

풀이

이번 문제는 카테고리를 너무 의식한 나머지 오래 걸렸던 문제입니다. 사실 크게 보면 DP가 맞긴 한데 일반적으로 생각하는 그런 DP는 아녔습니다.

 

일단 4개를 한 번에 고르는 경우의 수는 너무 많으니 두 개, 두 개씩 골라 합을 비교하는 방식으로 갑시다.

$a_i + a_j + a_k + a_l = W$

위의 식을

$a_i + a_j = W - (a_k + a_l)$

이렇게 생각할 수 있습니다.

 

다만 여기서 항상 $i, j, k, l$이 달라야 하는데, 이를 해결할 방법을 생각해봐야 합니다.

 

핵심은 모든 수가 중복되지 않는다는 조건입니다.

어떤 $i, j$에 대해, $w = a_i + a_j$라고 합시다. 

이때 $j \neq k$인 $k$에 대해, 항상 $w \neq a_i + a_k$라고 볼 수 있습니다.

즉, 어떤 무게를 만들 수 있는 여러 인덱스 쌍이 있어도 그 인덱스들은 절대 겹치지 않습니다.

 

그러므로 첫 $N^2$의 조합에서 특정 무게를 만들 수 있는 인덱스 쌍 중, 단 한 쌍만 저장해주도록 합시다.

그 후 $N^2$ 조합을 다시 돌리며 어떤 인덱스 쌍이 만들어내는 무게 $w_i$에 대해, $w_i$를 만들어낸 인덱스 쌍과 $W-w_i$를 만든 인덱스 쌍이 겹치는지만 확인해주면 됩니다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n, w;
int p[5555], d[444'444], d2[444'444];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> w >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    memset(d, -1, sizeof(d));
    memset(d2, -1, sizeof(d2));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int weight = p[i] + p[j];
            if (d[weight] == -1) {
                d[weight] = i;
                d2[weight] = j;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int weight = w - (p[i] + p[j]);
            if (weight > 400'000 || weight < 0 || d[weight] < 0) continue;
            if (d[weight] != i && d2[weight] != j && d[weight] != j && d2[weight] != i) {
                cout << "YES";
                return 0;
            }
        }
    }

    cout << "NO";
}