문제 : https://www.acmicpc.net/problem/16287
[알고리즘풀이]
1. N개의 집합에서 서로 다른 2개의 소포를 뽑는 모든 경우에 대해 무게의 합을 따로 Sum 배열에 저장한다.
또, Sum 배열에 몇 번 / 몇번 소포를 합했는지 Index를 저장한다.
2. Binary Search를 위해 Sum 배열을 Sorting 한다.
3. Sum 배열을 순회하며, Binary Search를 이용해 합이 W가 되는 경우를 다른 Sum 배열의 원소를 찾고,
이때, 저장된 Index를 확인해 W가 되는 2개의 Sum 원소가 서로 다른 4개의 소포가 합해진 경우면 "YES"를 출력하고
배열을 다 순회해도 합이 W가 되고 Index가 다 다른 경우를 못 찾는다면 "NO"를 출력한다.
[상세풀이]
단순하게 생각하면 N개의 집합에서 서로 다른 4개의 소포를 4중 for문을 이용해서 모두 뽑아서 확인하는 것이다.
하지만, 이러면 O(N^4)로 당연히 시간 초과 문제에 걸린다.
이 문제는 N이 최대 5000 이므로, 2중 for문은 시간 초과에 걸리지 않는다.
따라서, N개의 집합에서 서로 다른 2개의 소포를 뽑는 모든 경우에 대해 무게의 합을 Sum 배열에 저장하고,
이 S배열에서 2개를 뽑는 방법을 사용할 것이다.
( S 배열의 크기는 N개에서 서로 다른 2개를 순서 상관없이 뽑는 경우의 수로 (N * (N-1)) / 2가 된다. )
int A[5000];
pair<int, int> sum[12497500]; // 5000 * 4999 / 2
ex) A[5] = { 1, 2, 3, 4, 5 } 라고 하자.
그러면 S[10] = { 1 + 2, 1 + 3, 1 + 4, 1 + 5, 2 + 3, 2 + 4, 2 + 5, 3 + 4, 3 + 5, 4 + 5}를 담는다.
이때, W = 10이라고 하면, S[0] = 3 과 S[6] = 7을 합치면 10이 된다.
하지만 S[0]은 1,2 번 소포를 합친 것이고 S[6]은 2,5번 소포를 합친 것이므로 2번 소포를 두 번 인용하게 된다.
따라서 S배열에 어떤 소포를 합친 건지 Index도 저장해야 된다.
Index는 N이 최대 5000이므로 0 ~ 4999번 중에 하나고 최대 4자리 수이므로 다음과 같은 기법을 통해 저장할 수 있다.
int p = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
sum[p].second = i * 10000 + j;
sum[p++].first = A[i] + A[j];
}
}
sum[p].second에 'i 와 j번 째 소포를 합쳤습니다.'라는 정보를 담아줄 것입니다.
이때, i * 10000 + j 를 sum[p].second에 저장한다면 10000 이상의 자리는 i 를 10000 미만의 자리는 j를 나타냅니다.
ex) 1번, 4999번 소포를 합쳤다고 한다면 sum[p].second = 14999 가 되고 1 / 4999로 해석할 수 있다.
그 후, Sum 배열을 모두 순회하며 합쳤을 때, W가 되는 짝을 구해야 되는데,
Linear Search로는 P개의 Sum 배열에 대해 W가 되는 짝을 배열을 모두 순회하며 찾아야 되므로 O(P^2)이 된다.
Sum 배열은 N*(N-1) / 2 개의 원소를 가지고 있으므로 결과적으로 O(N^4)이 되므로
Binary Search를 이용해야 된다. 따라서, Sum 배열을 먼저 Sorting 해줘야 한다.
bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first < b.first)
return true;
else
return false;
}
sort(sum, sum + p, cmp);
그 후 Binary Search를 이용하고 Index를 확인해서 서로 다 다른 4개의 소포의 합이 W가 되는 경우를 찾아준다.
#include<iostream>
#include<algorithm>
using namespace std;
int A[5000];
pair<int, int> sum[12497500];
bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first < b.first)
return true;
else
return false;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int n, w;
cin >> w >> n;
for (int i = 0; i < n; i++) {
cin >> A[i];
}
int p = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
sum[p].second = i * 10000 + j;
sum[p++].first = A[i] + A[j];
}
}
sort(sum, sum + p, cmp);
for (int i = 0; i < p; i++) {
int left = 0, right = p - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (sum[i].first + sum[mid].first == w) {
int index[4] = { sum[i].second / 10000, sum[i].second % 10000, sum[mid].second / 10000, sum[mid].second % 10000 };
bool flag = false;
for (int j = 0; j < 4; j++) {
for (int k = j + 1; k < 4; k++) {
if(index[j] == index[k]) {
flag = true;
break;
}
}
if (flag)
break;
}
if (flag) {
break;
}
else {
cout << "YES\n";
return 0;
}
}
else if (sum[i].first + sum[mid].first < w)
left = mid + 1;
else
right = mid - 1;
}
}
cout << "NO\n";
return 0;
}