https://www.acmicpc.net/problem/2295
2295번: 세 수의 합
우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최
www.acmicpc.net
집합 U에 포함된 원소들 중 세 수를 골라 더한 a + b + c = d 값도 집합 U에 포함되는 가장 큰 d를 찾는 문제입니다.
N이 최대 1000개이므로 N^3으로 구하면 시간 초과가 뜨기 때문에 다른 방법을 생각해봅니다.
우선 이 문제에서 세 수를 고를 때 중복이 허락됩니다.
즉, U = {2, 3, 5, 10, 15}에서 5를 세 번 골라 5 + 5 + 5 = 15가 될 수 있다는 뜻입니다.
이것을 고려하여 문제에 접근합니다.
먼저 위에서 기술한 a + b + c = d를 조금 변형하면 a + b = d - c가 됩니다.
그러면 N^2으로 a + b의 모든 경우를 구할 수 있습니다. 구한 값들은 따로 벡터에 저장해둡니다.
그러면 N^2으로 d - c도 구할 수 있으며, 이분 탐색으로 a + b == d - c인 d를 구한다면
시간은 N^2 * logN으로 줄어들 수 있습니다.
물론 upper_bound - lower_bound를 이용하여 갯수를 구하여 풀 수도 있지만 최적의 해를 구하는 문제가 아니고,
정확한 값이 있는지 찾기만 하면 되기 때문에 일반적인 이분 탐색으로도 풀 수 있습니다.
d - c를 기준으로 a + b를 탐색 해야하므로 v를 정렬해줍니다.
그 다음 이분 탐색으로 v[m] == dc인 경우를 찾아주고, max인 d를 출력해줍니다.
그리고 문제에서 고려한 다른 부분입니다.
1. 이 문제에서 입력은 자연수만 올 수 있으므로 d - c <= 0인 경우는 미리 배제할 수 있습니다.
2. d의 최댓값을 출력해야 하므로 순회하면서 max를 사용해야 하지만 미리 list를 내림차순으로 정렬했으므로 찾는 즉시 list[i]를 출력해주시면 됩니다.
물론 이 두 가지를 모두 하지 않아도 AC를 받을 수 있습니다.
첫 번째 코드는 가지치기를 했고, a + b = d - c를 찾는 즉시 출력한 코드입니다. 역시 시간이 가장 빨랐습니다.
두 번째 코드는 가지치기를 하지 않았고, a + b = d - c를 찾는 즉시 출력하였습니다.
세 번째 코드는 가지치기를 했고, a + b = d - c인 모든 경우의 max를 구했습니다.
네 번째 코드는 가지치기를 하지 않았고, a + b = d - c인 모든 경우의 max를 구했습니다.
4개의 결과 모두 이 문제에서는 시간 차이가 별로 없을 수 있지만 범위가 커진다면 차이도 분명 커질 것입니다.
만약 테스트나 대회문제를 푼다면 두 가지를 모두 하는 것이 좋습니다.
상황에 맞는 알고리즘을 선택하고, 가지치기의 중요성을 깨닫게 하는 문제였습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1001
using namespace std;
vector<int> v;
int list[MAX];
int N;
void func() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
v.push_back(list[i] + list[j]);
}
}
sort(v.begin(), v.end());
int vsize = v.size();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int dc = list[i] - list[j];
if (dc <= 0) continue;
int l = 0;
int r = vsize - 1;
while (l <= r) {
int m = (l + r) / 2;
if (v[m] == dc) {
cout << list[i] << '\n';
return;
}
else if (v[m] > dc) {
r = m - 1;
}
else {
l = m + 1;
}
}
}
}
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> list[i];
}
sort(list, list + N, [](int a, int b) {
return a > b;
});
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > binarysearch' 카테고리의 다른 글
| boj 27977 킥보드로 등교하기 (4) | 2023.04.22 |
|---|---|
| boj 18113 그르다 김가놈 (0) | 2022.10.09 |
| boj 2110 공유기 설치 (0) | 2021.04.13 |
| boj 7453 합이 0인 네 정수 (0) | 2021.01.22 |
| boj 2143 두 배열의 합 (0) | 2021.01.22 |