[백준] 3649 로봇 프로젝트
✔️ 문제
✔️ 문제 이해
-
로봇의 구멍을 2개의 레고 조각으로 막아야 한다.
-
구멍을 막을 레고 조각 2개의 길이 합은 구멍의 너비와 정확히 일치해야한다.
-
이 문제의 테스트 케이스는 여러개이다. (불친절하게도 테스트 케이스 개수가 주어지지 않는다.)
-
각 테스트 케이스마다 구멍의 너비 x, 레고 조각의 개수 n, n개의 레고 조각에 대한 길이가 주어진다.
-
주어지는 구멍의 길이 단위는 cm 다. 레고 조각의 길이 단위는 nm 다. ( 1cm = 10000000nm )
-
각 테스트 케이스마다 아래와 같이 결과를 출력한다.
-
구멍을 막을 수 있는 두 조각이 없다면 “danger”을 출력한다.
-
구멍을 막을 수 있는 두 조각이 있다면 “yes” + “ 조각1길이” + “ 조각2길이” 를 출력한다.
-
구멍을 막을 수 있는 두 조각이 여러 개인 경우에는 두 조각의 길이 차이가 가장 큰 경우를 출력한다.
✔️ 알고리즘 설계
-
주어진 n개의 레고 조각들 중 하나를 선택한다. 나머지 조각들을 하나씩 선택해서 두 조각의 길이 합이 x가 되는지 확인한다.
-
나머지 조각을 하나씩 선택할 때 이분 탐색을 사용한다.
-
먼저 이분탐색을 위해 n개의 레고 조각을 길이 기준 오름차순으로 정렬한다.
-
두 조각의 길이 합이 x 보다 작으면 왼쪽을 탐색한다.
-
두 조각의 길이 합이 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) { // 두 조각의 길이 합이 x 보다 같거나 크다면, 오른쪽을 탐색한다.
if (size == x && idx != mid) { // idx != mid : 중복된 조각 선택을 막는다.
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 { // 두 조각의 길이 합이 x 보다 작으면 왼쪽을 탐색한다.
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); // 이분탐색을 위해 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 단위로 맞춰주는 부분에서 실수가 있었다.