[C++] BOJ(백준) 2473 세 용액

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

2473번: 세 용액

 

이분 탐색, 투 포인터 문제다.

 

'두 용액'의 업그레이드 버전이고 '합이 0' 의 업그레이드 버전이기도 하다.

세 용액의 특성값 합이 0에 가까워야 한다.

 

문제를 보자마자 떠올랐던 점은

1. 데이터 정렬

2. 투 포인터는 이중 for문으로 활용

3. 다른 하나의 값은 (투 포인터가 가리키는 값들의 합) * (-1) (sum)에 가까운 수

3. 이분 탐색으로 나머지 하나의 값 (zero 인덱스) 탐색

4. 합이 -1인 것과 1인 것은 동일하게 취급 -> 절댓값 사용

4-1. zero를 탐색하고 sum 보다 크거나 같은 수를 우선적으로 찾음

4-2. arr[zero]가 sum과 같으면 세 용액의 합이 0이므로 출력 후 종료

4-3 크다면 arr[zero]대해 계산하고, arr[zero-1]에 대해 한 번 더 계산

 

풀면서 생겼던 오류

1. 이분 탐색 범위 : 투 포인터를 양 끝에서 모이는 것에 익숙해져 이분 탐색의 범위를 i + 1 ~ j 번째 인덱스로 잡음

=> 답이 큰 확률로 0 0 0만 나옴...

2. 반복문의 범위 : j를 n - 1까지 탐색했는데 이분 탐색 범위가 j + 1 ~ n 이므로 j가 n - 1일 때 배열의 범위를 넘어 섬

=> 0 2 5 처럼 의미 없는 0이 생김

3. 모든 값이 음수인 경우 : 투 포인터의 합에 -1을 곱하면 양수, 양수를 찾으려면 배열의 범위를 벗어난 n번째 인덱스 접근

=> 더 작은 값이 있으나 큰 값을 출력함

==> 이 부분의 경우 이분 탐색으로 찾은 인덱스의 값이 n일 경우 1을 빼 가장 큰 음수를 가리키게 함

4. 탐색한 값의 인덱스(zero)가 j+1인 경우 : 세 용액의 합이 0이 아닌 경우 zero - 1에 대해 계산을 하는데 이 때 j번째 인덱스가 두 번 계산되는 오류 발생

==> 예외처리

 

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll arr[5000];

int main() {
	int n;		cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];

	// 이분 탐색을 위한 정렬
	sort(arr, arr + n);

	// 합이 0에 가까운 세 용액 저장, 정렬을 위해 배열로 선언
	int re[3] = { 0 };
	ll mi = 3000000001;

	for (int i = 0; i < n - 2; i++) {
		for (int j = i + 1; j < n - 1; j++) {
			// 두 용액의 합 * (-1)
			ll sum = -(arr[i] + arr[j]);
			// j번째 다음 값부터 sum 탐색
			int zero = lower_bound(arr + j + 1, arr + n, sum) - arr;

			// 인덱스가 배열의 범위를 벗어나면 -1
			if (zero == n) zero--;

			// zero인덱스의 값과 sum이 같으면 세 용액의 합이 0이므로 출력 후 종료
			if (arr[zero] == sum) {
				// 세 용액 값 저장
				re[0] = arr[i];	re[1] = arr[zero];	re[2] = arr[j];
				sort(re, re + 3);
				cout << re[0] << " " << re[1] << " " << re[2];
				return 0;
			}

			// arr[zero]가 sum보다 큰 경우
			if (mi > abs(-sum + arr[zero])) {
				mi = abs(-sum + arr[zero]);
				re[0] = arr[i];	re[1] = arr[zero];	re[2] = arr[j];
			}

			// arr[zero - 1]에 대해 계산
			if (mi > abs(-sum + arr[zero - 1])) {
				// zero가 j+1인 경우 zero - 1은 j가 됨, 같은 값에 대해 두 번 계산하므로 예외처리
				if (zero - 1 == j) continue;
				mi = abs(-sum + arr[zero - 1]);
				re[0] = arr[i];	re[1] = arr[zero - 1];	re[2] = arr[j];
			}
		}
	}
	// 정렬 후 출력
	sort(re, re + 3);
	cout << re[0] << " " << re[1] << " " << re[2];
}

[]~(￣▽￣)~*