세 수의 합( BOJ 2295 )

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

2295번: 세 수의 합

 

문제 파악하기

N개의 숫자로 이루어진 집합 U에서 3개의 숫자를 적절하게 선택해서 집합 U에 있는 값 중 만들 수 있는 가장 큰 값을 만드는 문제입니다. N의 개수가 최대 1,000개이기 때문에 O(n³)알고리즘으로는 시간초과가 나오게 됩니다. 그렇다면 어떤 알고리즘을 사용해서 시간 복잡도를 줄일 수 있을까요? 여기서는 3개의 숫자의 합을 구하는 수식을 나눌 필요가 있습니다.

 

문제 해결하기

우선, 3개의 숫자(a, b, c)를 사용해서 집합 U의 값(k)를 아래와 같이 만들었다고 가정해보겠습니다.

a + b + c = k --- (1)

 

위의 식을 그대로 알고리즘에 도입하면 우리는 3중 반복문으로 구현하게 됩니다. 하지만 N의 값이 크기 때문에 3중 반복문을 사용한 알고리즘으로는 1초라는 시간은 턱없이 부족합니다. 따라서, 우리는 위 식을 다음과 같이 바꿔보겠습니다.

a + b = k - c --- (2)

 

이렇게 식을 바꾸면 우리는 2중 반복문 2개를 사용하는 알고리즘을 만들 수 있습니다. 첫 번째 반복문은 두 숫자의 합을 구하고, 두 번째 반복문은 두 수의 차를 구한 다음에, 지금 구한 값(두 수의 차)이 이전 반복문에서 만들어진 값인지 확인해보면 됩니다. N이 최대 1,000개이기 때문에 2중 반복문은 충분히 제한시간 안에 작동하며, 2중 반복문 2개 역시 제한시간 안에 작동합니다. 이렇게 반복문의 횟수를 줄이면 문제를 효율적으로 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

우선, 첫 번째 소스코드는 해시테이블을 사용해 모든 합을 확인하는 알고리즘입니다.

#include <stdio.h>
#include <map>
#include <vector>
#define NMAX 1010
using namespace std;
 
int N, t;
vector< int > inp, psum;
 
int ret;
map< int, int > check;
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d", &t);
        inp.push_back(t);
    }
 
    for(int i=0;i<N;i++) {
        for(int j=i;j<N;j++) {
            psum.push_back(inp[i]+inp[j]);
 
            check[inp[j]-inp[i]] = inp[j];
        }
    }
 
    for(int val:psum) ret = max(ret, check[val]);
 
    printf("%d", ret);
}

 

두 번째 소스코드는 위의 (2)번 식을 직관적으로 구현한 알고리즘입니다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, t;
vector< int > inp, psum;
 
int ret;
 
bool checkValue(int val) {
    int l,r,mid;
 
    l=0; r=psum.size()-1;
    while(l<=r) {
        mid = (l+r)/2;
 
        if(psum[mid] == val) return 1;
        else if(psum[mid] < val) l = mid+1;
        else r = mid-1;
    }
 
    return 0;
}
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d", &t);
        inp.push_back(t);
    }
    sort(inp.begin(), inp.end());
 
    for(int i=0;i<N;i++) {
        for(int j=i;j<N;j++) {
            psum.push_back(inp[i]+inp[j]);
        }
    }
    sort(psum.begin(), psum.end());
 
    for(int i=N-1;i>=0 and !ret;i--) {
        for(int j=i;j>=0 and !ret;j--) {
            if(checkValue(inp[i]-inp[j])) {
                ret = inp[i];
            }
        }
    }
 
    printf("%d", ret);
}

후기

Meet in Middle 알고리즘을 연습하기에 적절한 문제라고 생각합니다. 저 역시 이 문제를 통해 이 알고리즘의 작동방식을 이해하게 되었습니다. 이 알고리즘을 좀 더 연습하고 싶다면 이 문제(https://www.acmicpc.net/problem/1450)가 적절하다고 생각합니다. 참고로 알고리즘의 개념을 배울 때에는 이 영상(https://www.youtube.com/watch?v=57SUNQL4JFA)이 도움이 되었습니다.