Memo
•
입력으로 받은 값들을 sorting 합니다.
•
앞에서 부터 하나의 용액을 정해놓고, 나머지 두 용액을 정해놓은 기준 오른쪽 부분에서 찾습니다.
•
포인터를 맨 왼쪽과 맨 오른쪽에 두고, 현재 기준으로 정해진 용액들의 합이 0보다 작으면 왼쪽 포인터를 증가시키고, 0보다 크면 오른쪽 포인터를 감소시킵니다. sorting이 되어있기 때문에 가능한 작업입니다.
어려웠던 부분
if (std::abs(val) < std::abs(max_val))
{
max_val = val;
ans[0] = sol[i];
ans[1] = sol[left];
ans[2] = sol[right];
}
C++
복사
위 부분을 원래
if (std::abs(val) >= std::abs(max_val))
break;
C++
복사
로 작성했었는데, 이 경우 최소값이 나올 수 있음에도 불구하고 작업을 종료하기 때문에 종료 조건은 오로지 left == right 로 해야합니다.
Code
제출 날짜
@3/30/2021
메모리
2180 KB
시간
28 ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
typedef long long ll;
std::vector<ll> sol;
ll ans[3];
ll max_val;
size_t N;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
input_faster();
std::cin >> N;
sol.resize(N);
for (size_t i = 0 ; i < N ; i++)
std::cin >> sol[i];
max_val = 999999999999999;
}
void solve()
{
int _N, left, right;
ll val;
_N = N;
std::sort(sol.begin(), sol.end());
for (int i = 0 ; i < _N - 2 ; i++)
{
left = i + 1;
right = _N - 1;
while (true)
{
if (left == right)
break;
val = sol[i] + sol[left] + sol[right];
if (std::abs(val) < std::abs(max_val))
{
max_val = val;
ans[0] = sol[i];
ans[1] = sol[left];
ans[2] = sol[right];
}
if (val == 0)
break;
if (val < 0)
left += 1;
else
right -= 1;
}
}
}
void print_val()
{
std::sort(ans, ans+3);
for (int i = 0 ; i < 3 ; i++)
std::cout << ans[i] << " ";
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사