문제
풀이
-10억부터 10억까지 숫자가 주어지고 세 수의 합이 가장 0에 가까운 수들을 찾는 문제이다.
입력은 정렬된 상태로 주어지지 않으니, 입력을 받고 먼저 정렬을 한다.
반복문으로 배열에 접근하면서 투 포인터를 사용하였다.
abs(arr[i] + arr[low] + arr[high])가 가장 0에 가까운 세 수를 찾으면 되는데,
10억 + 10억 + 10억은 int로 받을시에 오버플로가 나서 long long으로 받아주었다.
코드
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits.h>
using namespace std;
int n;
int arr[5001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(arr, arr + n);
long long sum = LLONG_MAX;
int answer1, answer2, answer3;
for (int i = 0; i < n-2; i++) {
int low = i + 1;
int high = n - 1;
while (low != high) {
long long tempSum = (long long)arr[i] + (long long)arr[low] + (long long)arr[high];
if (abs(tempSum) < sum) {
sum = abs(tempSum);
answer1 = arr[i];
answer2 = arr[low];
answer3 = arr[high];
}
if (abs(arr[i]) > abs(arr[low] + arr[high]))
low++;
else
high--;
}
}
cout << answer1 << " " << answer2 << " " << answer3;
return 0;
}
'Koala - 11기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/Python] 1337 올바른 배열 (0) | 2023.07.30 |
---|---|
[백준/C++] 2470번 : 두 용액 (0) | 2023.07.30 |
[백준/C++] 2003번 : 수들의 합 2 (1) | 2023.07.30 |
[백준 / Python] 1253번 : 좋다 (0) | 2023.07.30 |
[C++] 백준 15686번: 치킨 배달 (0) | 2023.07.30 |