백준 2295: 세 수의 합 [C/C++]

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

2295번: 세 수의 합

 

1번 : Map을 이용한 코드

#include <iostream>
#include <algorithm>
#include <map>
#define fastio() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n, ans, lis[1010];
map<int, bool> m;
int main() {
    fastio();
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> lis[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (m.find(lis[j] - lis[i]) != m.end()) ans = lis[j] < ans ? ans : lis[j];
            m.insert({lis[i] + lis[j], true});
        }
    }
    cout << ans;
    return 0;
}

00 : 18 : 25

 

2번 : Binary Search를 이용한 코드

#include <iostream>
#include <algorithm>
#define fastio() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
long long n, k, ans, lis[1010], acc[1111111];
int main() {
    fastio();
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> lis[i];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) acc[++k] = lis[i] + lis[j];
    sort(acc + 1, acc + k);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (binary_search(acc + 1, acc + k, lis[i] - lis[j])) ans = ans < lis[i] ? lis[i] : ans;
    cout << ans;
    return 0;
}
 

00 : 07 : 12