BOJ 2295 - 세 수의 합

2295번: 세 수의 합 (acmicpc.net)

2295번: 세 수의 합

 

접근 방법

 

백트래킹, 브루트포스말고는 어떻게 풀어야할지 감이 안잡혔다.

그래서 결국 알고리즘 분류를 봤다...

 

이 문제에서 어떻게하면 이분탐색으로 풀수있을까 많이 생각해보았다.

 

무엇을 기준으로 대소비교를 할 것인가?

 

처음엔 원소의 인덱스를 기준으로 생각해보려고 했지만, 해당 원소의 더한 값을 구하려면 이전 원소들을 모두 3개씩 더해야 한다. 그리고 무엇을 기준으로 Left, Right를 할 것인지도 정하기 힘들다.

 

x+y+z = k 인 것 중 가장 큰 값을 구하면 된다.

만약, x,y가 더해져 있고 여기에 z를 더하면 비교가 가능하지 않을까 라는 생각을 했다.

 

그래서 x와 y를 미리 다 구해놓고 (pairSum)

이것을 기준으로 z를 더했을 때, k보다 작으면 r=m-1을 하고

만약 z을 더했을 때, k보다 크면 l = m+1을 하면된다.

 

따라서, 다음과 같은 식이 나온다.

 

int m = (l + r) / 2;
int XPlusY = pairSum[m];

if (XPlusY < k - z) {
	l = m + 1;
}
else if (XPlusY > k - z) {
	r = m - 1;
}
else {
    res = max(res, k);
    break;
}

K와 Z의 경우,  집합의 원소들이기 때문에 2차원 for을 이용하여 구하면 된다.

 

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<map>

#define MAX_NUM 1000001

using namespace std;

int n;
vector<int> v;
vector<int> pairSum;
int res = 0;
int l, r;


int main() {
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			pairSum.push_back(v[i] + v[j]);
		}
	}

	

	sort(pairSum.begin(), pairSum.end());

	int res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int k = v[i];
			int z = v[j];
			
			l = 0;
			r = pairSum.size() - 1;

			while (l < r) {
				int m = (l + r) / 2;
				int XPlusY = pairSum[m];

				if (XPlusY < k - z) {
					l = m + 1;
				}
				else if (XPlusY > k - z) {
					r = m - 1;
				}
				else {
					res = max(res, k);
					break;
				}
			}
		}
	}
	cout << res;
}

진짜 신박한 이분탐색 문제였다...