boj 2295 세 수의 합

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

2295번: 세 수의 합

집합 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개의 결과 모두 이 문제에서는 시간 차이가 별로 없을 수 있지만 범위가 커진다면 차이도 분명 커질 것입니다.

만약 테스트나 대회문제를 푼다면 두 가지를 모두 하는 것이 좋습니다.

상황에 맞는 알고리즘을 선택하고, 가지치기의 중요성을 깨닫게 하는 문제였습니다.

 

 

#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;
}