티스토리 뷰

BOJ 문제 링크: https://www.acmicpc.net/problem/16287

 

아는 분의 블로그(링크)에 이 문제에 대한 풀이가 올라온김에 풀어보았다. 해당 블로그에서는 $O(N^2 \log N)$ 풀이를 설명하고 있다. 이 글에서는 $O(N^2 + \max\{A_i\})$ 풀이와 다른 형태의 $O(N^2 \log N)$ 풀이를 설명한다.

Problem

서로 다른 $N$개의 정수 $\{A_i\}_{i=1}^{N}$가 주어진다. 이들 중 4개를 골라 합하여 $W$가 될 수 있는지 판단하는 문제이다. $A_i \le 200,000$이고, $N \le 5,000$이다.

Solution

$A_i + A_j + A_k + A_l = W$인 $i, j, k, l$의 존재성을 찾는 문제인데, 이 문제의 경우 식이 대칭적이다. 대칭적인 식이 나오는 수학문제를 해결하는 과정을 생각해보면, 대개 각 변수에 대소관계를 주고, 대소관계를 이용해 변수의 범위를 제한하여 해결한다. 이 발상을 문제에 활용해보자.

일반성을 잃지 않고, $i < j < k < l$이라 가정할 수 있다. $i, j$의 값은 $k$에 의해 제한되어 있으니, $k$를 $1, 2, 3, \cdots, N$까지 차례로 늘려가며 해결해보자.

 

$k = k_0$라 하자. 만약, $i < j < k_0$인 모든 $(i, j)$에 대해 $A_i+A_j$의 값으로 가능한 것을 미리 구해놨다면, $k = k_0$인 $i, j, k, l$의 존재성은 $l$을 늘려가며 $O(N-k_0)$ 시간에 해결할 수 있다.

...더보기

엄밀하게 말하자면, Counting sort와 비슷하게 $4 \max \{ A_i \}$ 정도 크기의 bool 배열을 잡고 메모해 놓았다면, $O(N-k_0)$이며, std::set과 같은 자료구조에 저장해뒀다면, $O((N-k_0) \log k_0)$이다. 이 풀이에서는 전자의 형태로 값을 메모해놓았다고 가정한다.

이제, $k = k_0+1$일 때 "추가로 가능해지는" $(i, j)$들을 생각해보면, $j = k_0$를 만족한다. 따라서, $k = k_0 \rightarrow k = k_0+1$로 넘어가기 전에, $i < k_0$에 대해 $A_i + A_{k_0}$로 가능한 값들을 추가로 업데이트 해주면 되며, 이 과정의 시간복잡도는 $O(k_0)$이다.

 

따라서, $k$에 대한 loop를 돌 때 한 단계마다 걸리는 시간은 $O(k) + O(N-k) = O(N)$이 된다. loop를 도는 총 횟수가 $N$번 이고, 처음에 메모이제이션을 위한 배열을 잡는 시간복잡도가 $O(\max\{A_i \}$이므로, 총 시간복잡도는 $O(N^2 + \max\{A_i\})$가 된다. 만약, 메모이제이션을 위한 배열을 잡지 않고, std::set과 같은 자료구조를 활용하여 해결하면, $O(N^2 \log N)$의 시간복잡도에 해결하게 된다.

 

구현 1: 배열을 통한 메모이제이션 활용

#include <bits/stdc++.h>
using namespace std;

int N, W, A[5005];
bool chk[800001];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> W >> N;
    for (int i=0; i<N; i++) cin >> A[i];
    sort(A, A+N);
    for (int k=0; k<N; k++){
        for (int l=k+1; l<N; l++){
            if (A[k]+A[l] > W) break;
            if (chk[W-A[k]-A[l]]){
                cout << "YES" << endl;
                return 0;
            }
        }
        for (int j=0; j<k; j++){
            chk[A[j]+A[k]] = true;
        }
    }
    cout << "NO" << endl;
}

 

구현 2: std::set 활용

#include <bits/stdc++.h>
using namespace std;

int N, W, A[5005];
set<int> S;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> W >> N;
    for (int i=0; i<N; i++) cin >> A[i];
    sort(A, A+N);
    for (int k=0; k<N; k++){
        for (int l=k+1; l<N; l++){
            if (A[k]+A[l] > W) break;
            if (S.count(W-A[k]-A[l])){
                cout << "YES" << endl;
                return 0;
            }
        }
        for (int j=0; j<k; j++){
            S.insert(A[j]+A[k]);
        }
    }
    cout << "NO" << endl;
}

P.S. 모든 A값이 다르다는 assertion을 넣은 코드가 BOJ에서 런타임에러를 띄운다. BOJ의 데이터가 틀렸을 가능성도 있다.

 

댓글
댓글쓰기 폼
공지사항
Total
20,231
Today
24
Yesterday
25