설명없음
백준 2295: 세 수의 합 [C/C++]
치킨먹고싶어요
2022. 6. 16. 14:48
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
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;
}
|
cs |
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;
}
|
cs |
00 : 07 : 12