백준 16287 Parcel

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

 

MITM? .. 모르겠다

분할 정복으로 풀었다

 

4개를 고르는 경우를 모두 살펴야 하는데 $O(N^2)$까지 되는 제한이다.

BOJ 9007 같은 느낌으로 일단 2개를 고르는 경우를 모두 구한 뒤 이를 잘 활용해 답을 구하고 싶어진다. 

$w$ 범위가 너무 크지 않으니 2개를 고르는 모든 경우에 대해 고른 두 수의 합을 인덱스로 사용하는 체크 배열을 만들면 합치는 과정은 $O(N^2)$ 정도에 할 수 있다. 

 

2개를 고른 두 경우를 합칠 때 선택한 원소가 같으면 안 되니 배열을 반으로 나누어 한 쪽에서 2개, 다른 쪽에서 2개를 선택한다는 생각을 해볼 수 있다. 반으로 나누면 한 쪽에서 4개 모두 고르는 경우는 분할 정복처럼 처리할 수 있으니 양쪽에서 1개 / 3개, 2개 / 2개, 3개 / 1개 고르는 경우를 처리하면 된다. 길이가 $O(N)$인 구간을 $O(N^2)$ 정도에 처리할 수 있다면 전체 시간복잡도도 $O(N^2)$이므로 (마스터 정리) 문제를 풀 수 있다.

 

양 쪽에서 2개씩 고르는 경우의 수는 체크 배열을 활용하여 처리할 수 있다. 한 쪽에서 하나, 다른 쪽에서 3개를 고르는 경우는 양쪽 배열에서 하나씩 고르는 모든 조합을 살펴보며 처리할 수 있다. 3개를 고르는 쪽에서 같은 수를 고르는 경우를 확인하기 위해 체크 배열에 고른 두 수 중 더 작은 인덱스를 저장할 수 있다.

 

현재 구간에 대한 작업이 끝나고 재귀 호출하기 전에 체크 배열을 초기화해주어야 한다. 

 

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0), cin.tie(nullptr)
using namespace std;
const int S = 5000 + 50;
 
int W, N, A[S], chk[2][800000], ans;
 
void f(int l, int r){
    if (r-l+1 < 4 or ans) return;
    int mid = l+r >> 1;
    for (int i = l; i <= mid; i++){
        for (int j = i+1; j <= mid; j++)
            chk[0][A[i]+A[j]] = max(chk[0][A[i]+A[j]], i);
    }
    for (int i = mid+1; i <= r; i++){
        for (int j = i+1; j <= r; j++){
            chk[1][A[i]+A[j]] = max(chk[1][A[i]+A[j]], i);
            if (A[i]+A[j] < W and chk[0][W-A[i]-A[j]]){
                ans = 1;
                return;
            }
        }
    }
    for (int i = l; i <= mid; i++){
        for (int j = mid+1; j <= r; j++){
            if (A[i]+A[j] < W and (chk[0][W-A[i]-A[j]] > i or chk[1][W-A[i]-A[j]] > j)){
                ans = 1;
                return;
            }
        }
    }
    for (int i = l; i <= mid; i++){
        for (int j = i+1; j <= mid; j++)
            chk[0][A[i]+A[j]] = 0;
    }
    for (int i = mid+1; i <= r; i++){
        for (int j = i+1; j <= r; j++)
            chk[1][A[i]+A[j]] = 0;
    }
    f(l, mid);
    f(mid+1, r);
}
 
int main() {
    fast;
 
    cin >> W >> N;
    for (int i = 1; i <= N; i++) cin >> A[i];
    f(1, N);
    cout << (ans ? "YES" : "NO");
}