https://www.acmicpc.net/problem/4373
4373번: 수집합
문제 정수 집합 S가 주어졌을 때, a + b + c = d를 만족하는 가장 큰 d를 구하는 프로그램을 작성하시오. 이때, a, b, c, d는 S의 원소이며, 서로 다른 수이다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 집합 S의 크기 n(1 ≤ n ≤ 1000)이 주어진다. 다음 줄부터 n개의 줄에는 집합 S의 원소(-536870912와 ~ +536870911)가 하나씩 주어진다. 집합의 원소는 중복되지
www.acmicpc.net
백준저지 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();
}
}'알고리즘 & Problem Solving' 카테고리의 다른 글
| 백준 12877번 문제 먹이 사슬 풀이 (0) | 2020.01.25 |
|---|---|
| 회사에서 채용시 알고리즘 문제해결능력을 강조하는 이유는 무엇일까? (2) | 2020.01.24 |
| 삼성 SW 역량테스트 및 A형 시험 준비하기 (8) | 2020.01.03 |
| 코딩테스트 언어 선택 팁 (0) | 2019.12.12 |
| Codeforces Round #601 (Div 2) 참가 후기 (0) | 2019.11.22 |
