Search
Duplicate

세 용액

주차
0
문제번호
2473
언어
티어
골드
유형
이분탐색
투 포인터
nj_Blog
nj_상태
완료
이해도
풀이
사람
이해도 2
13 more properties

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++
복사