백준 BOJ 3649 - 로봇 프로젝트

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

3649번: 로봇 프로젝트

이분탐색 문제

std::unordered_map 쓰면 날로먹을수있을거같이 생겨먹었는데

왠지 모를 이유로 잘 안풀려서 이분탐색으로 해결했다.

둘의 합이 X*10000000 = K 가 되게 해야하기 때문에,

어떤 한 수를 정해줬다면 해당 수와 더해서 K가 되게끔 하는 수를

O(logN) 시간에 찾아야 한다.

찾아내는 가장 좋은 방법은 이분탐색.

 

이때, 어떤 한 수 a가 한개밖에 없으면서 a+a가 K인 경우,

원래는 a가 한개뿐이므로 만들어질 수 없는 경우이기 때문에

이부분을 고려해줘야 한다.

 

입력으로 받은 $l_i$ 들을 미리 정렬해주면

정답을 처음 찾았을때 자동적으로 해당 답이 $| l_1 - l_2 |$ 의 최댓값이 되므로

그대로 출력해주면 된다.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

vector<int> v;
bool flag = false;

int main(){
	int X,N,l;
	while(cin >> X){
		cin >> N;

		v.clear();
		flag = false;
		
		X *= 10000000;
		for(int i=0; i<N; i++){
			cin >> l;
			v.push_back(l);
		}
		
		sort(v.begin(), v.end());
		
		for(int i=0; i<N; i++){
			int tmp = X-v[i];
			int idx = lower_bound(v.begin(), v.end(), tmp) - v.begin();
			
			if(i != idx && v[idx] == tmp){
				flag = true;
				pair<int,int> p = {min(v[i],X-v[i]), max(v[i],X-v[i])};
				cout << "yes " << p.x << " " << p.y << "\n";
				break;
			}
		}
		
		if(!flag) cout << "danger\n";
	}
	return 0;
}