백준 4373번 문제 수집합 풀이

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

4373번: 수집합

백준저지 4373번 문제 수집합 문제 풀이입니다.

 

문제 접근

//(a+b+c=d//) 인 최대 //(d//) 를 구해야 한다. 좌항에서 더하는 수가 3개 밖에 안되고 //(N//)이 1000이므로 뭔가 비벼볼 만 하다는 느낌이 매우 든다.

 

양 항에 //(c//)를 빼서  //(a+b=d-c//)꼴로 만들어 보자.

 

모든 //(a+b//)쌍을 만들면 //(O(N^2)//)이므로 reasonable 한 시간으로 다 만들 수가 있다.

마찬가지로 //(d-c//)쌍도 같은 시간 복잡도로 만들 수 있다.

 

그면 그 두 값이 같은 경우를 모두 체크해주면 된다.

 

바이너리 서치 풀이

일단 첫 번째로 떠올랐던 풀이는 //(a+b//) 쌍들은 정렬해서 두고, //(d//) 와 //(c//)값에 대해서는 2중 포문으로 모두 돌면서 확인하면서 바이너리 서치로 맞는 값이 있는지를 확인하는 풀이를 생각해 보았다.

 

그런데 이렇게 할 경우 일단 a,b,c,d가 다 다른 값이어야 하는데 이를 체크하는 로직이 조금 번거로워 질 수가 있다는 생각이 들었다.

 

//(a+b//)가 같은 값이되, 각각 //(a//)와 //(b//)값이 다른 경우가 생길 시, 그런 경우를 다 체크해줘야 하기 때문이다.

 

예컨데, 입력값이 1,2,3,4,9 가 있을 시 (1,4)=>5 와 (2,3)=>5가 있는데, 

//(a+b//)값을 5로 잡고, //(c//)값을 4로 잡아서 //(a+b+c=9//)라고 하고싶다고 해 보자.

그러면 이때 //(a+b//)에는 //(c//)값에 해당하는 4가 중복되면 안되기 때문에, (1,4)로 5가 되는지 (2,3)로 5가 되는지를 모두 체크해야 한다.

 

이 구현부분이 좀 바이너리써치 치고 귀찮았고, 요걸로 투닥투닥해버리려다가 자꾸 WA가 났다.

 

그리고 이 경우 시간복잡도는 //(O(N^2lg(N^2))//)로 정렬을 하고, 바이너리 써치를 하기 때문에 //(O(N^2lg(N^2))//)가 된다.

둘을 합친 값이 시간복잡도가 된다(big oh notation에서는 걍 //(O(N^2lg(N^2))//)이긴 하다)

 

이 풀이는 구현에서 fail되엇다..;;

 

중복 수가 나올 수 있다는 점이 구현하는데 귀찮기도 하고 뭔가 복잡했다. 나이스하게 처리할 방법이 잘 생각나지 않아서 적당히 짜보다가 WA나와서, 이 풀이법은 버렸다.;

 

투 포인터 풀이

투 포인터로도 접근이 가능한데, //((a,b)//)쌍만 만들어서 정렬해놓는게 아닌, //(c,d//)쌍도 모두 만들어서 정렬해놓는다. 

그리고 투 포인터로 쭉죽 밀어가면서 같은 값이 나오는지를 //(O(N^2)//)로 알아내면 된다. 이런 경우, 같은 값이 나왔을 때만 같은 원본 값을 사용했는지를 체크하면 되서, 중복 체크 로직이 훨씬 쉽고 간단해진다.

 

시간복잡도 상으로는 바이너리 서치와 같은 //(O(N^2lg(N^2)//)이 된다. 투 포인터를 하는 부분이 //(O(N^2)//)로light-weght 하긴 한데, 소팅을 두번 해야 하므로 사실상 거의 비슷할듯하다

 

구현상 유의할 점

약간 유의해야 할 점은 //(a+b//)쌍은 순서가 바뀌어도 교환법칙이 성립하지만, //(d-c//)는 순서가 바뀌면 값이 음수 반전이 되므로 유의해야 한다. 그리고 숫자값 범위가 음수도 포함되어 있으므로 //(d-c//)가 반전되는 경우도 잘 체크해야 한다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int n;
int a[1003];
#define NOANSWER -2147483600
struct Data {
	int val, p, q; //(a,b) or (d,c)
	bool operator<(const struct Data& rhs) const {
		return val < rhs.val;
	}
	bool operator>(const struct Data& rhs) const {
		return val > rhs.val;
	}
};
Data ab[1000006];
Data dc[1000006];
void solve() {
	for (int i = 0; i < n; i++) {
		scanf("%d", a + i);
	}
	int abcnt = 0;
	int dccnt = 0;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			ab[abcnt].val = a[i] + a[j];
			ab[abcnt].p = i;
			ab[abcnt].q = j;
			abcnt++;
		}
	}
	sort(ab, ab + abcnt);
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			dc[dccnt].val = a[j] - a[i];
			dc[dccnt].p = j;
			dc[dccnt].q = i;
			dccnt++;
		}
	}
	sort(dc, dc + dccnt);

	int ans = NOANSWER;
	int p, q;
	p = q = 0;
	while (p < abcnt && q < dccnt) {
		auto& l = ab[p];
		auto& r = dc[q];
		if (l.val > r.val) {
			q++;
		}
		else if (l.val < r.val) {
			p++;
		}
		else {
			if (l.p != r.p && l.p != r.q && l.q != r.p && l.q != r.q) {
				ans = max(ans, a[r.p]);
			}
			if (p < q) p++;
			else q++;
		}
	}
	reverse(dc, dc + dccnt);

	while (p < abcnt && q < dccnt) {
		auto& l = ab[p];
		auto& r = dc[q];
		if (l.val > -r.val) {
			q++;
		}
		else if (l.val < -r.val) {
			p++;
		}
		else {
			if (l.p != r.p && l.p != r.q && l.q != r.p && l.q != r.q) {
				ans = max(ans, a[r.q]);
			}
			if (p < q) p++;
			else q++;
		}
	}
	if (ans == NOANSWER) {
		puts("no solution");
	}
	else {
		printf("%d\n", ans);
	}
}
int main() {
	while (true) {
		scanf("%d", &n);
		if (!n) return 0;
		solve();
	}

}