[백준] 3649 로봇 프로젝트

✔️ 문제 링크

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

3649번: 로봇 프로젝트

---

✔️ 문제 이해

◾ 로봇의 구멍을 2개의 레고 조각으로 막아야 한다.

◾ 구멍을 막을 2개의 레고 조각 길이의 합은 구멍의 너비와 정확히 일치해야한다.

◾ 테스트 케이스는 여러개이다.

◾ 각 테스트 케이스마다 구멍의 너비 x, 레고 조각의 개수 n, 각 레고 조각의 길이가 주어진다.

◾ 레고 조각의 길이는 나노미터 단위이다. ( 1cm = 10000000nm )

◾ 각 테스트 케이스마다 결과를 출력한다. 구멍을 막을 수 있는 두 조각이 없다면 "danger"을 출력한다.

◾ 구멍을 완벽하게 막을 수 있는 두 조각이 있다면 "yes 레고조각길이1 레고조각길이2" 를 출력한다.

◾ 정답이 여러개인 경우에는 |레고조각길이1 - 레고조각길이2| 가 가장 큰 것을 출력한다. 

---

✔️ 설계

◾ 주어진 레고 조각들중 하나를 뽑고 다른 조각을 골라서 두 조각의 길이 합이 x가 되는지 확인한다.

◾ 다른 하나의 조각을 고를때 이분탐색을 사용한다.

◾ 이분탐색을 위해 주어진 레고 조각들을 길이 기준으로 오름 차순 정렬한다. 

---

👨🏻‍💻 소스 코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

int arr[1000000];
int x, n;
vector<int> v;
int ret = -1;


// idx번째 블록과 합쳤을때 길이가 x가 되는 블록을 이분탐색으로 찾는다.
void find(int idx) {
	int low = 0, high = n;
	
	while (low <= high) {
		int mid = (low + high) / 2;
		int size = arr[idx] + arr[mid]; // 두 블록을 합쳤을 경우.

		if (size >= x) {
			if (size == x && idx != mid) { // 두 블록의 합이 x이고, 중복된 블록 선택이 아닐때.
				if (abs(arr[idx] - arr[mid]) > ret) { 
					ret = abs(arr[idx] - arr[mid]);
					v.clear();
					v.push_back(idx);
					v.push_back(mid);
				}
			}
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}

}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	while (cin >> x) {

		// 매 테스트 케이스마다 값 초기화.
		memset(arr, 0, sizeof(arr));
		v.clear();
		ret = -1;

		x *= 10000000; // 나노 단위로 맞춰준다.

		cin >> n;

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

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

		for (int i = 0; i < n; i++) { // i번째 블록과 다른 블록 조합을 찾아본다.
			find(i);
		}

		if (v.empty()) // 결과가 없을 경우.
			cout << "danger" << endl;
		else { // 결과가 있을 경우, 오름차순으로 출력한다. 
			sort(v.begin(), v.end());
			cout << "yes " << arr[v[0]] << " " << arr[v[1]] << endl;
		}
	}

	return 0;
}

---

✔️ 문제 회고

◾ 테스트 케이스 개수가 주어지지 않아서 당황했다. while문에 cin >>x 을 넣음으로서 입력이 종료될때까지 프로그램이 실행되게 했다. 

◾ cm 단위를 nm 단위로 맞춰줘야했다.