[백준 3649] 로봇 프로젝트 (C++)

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

문제

---

상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.

구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다.

지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오.

 

입력

---

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 구멍의 너비 x (1 ≤ x ≤ 20, x는 정수)가 주어진다. x의 단위는 센티미터이다.

다음 줄에는 물리 실험실에 있는 레고 조각의 수 n이 주어진다. (0 ≤ n ≤ 1000000)

다음 n개의 줄에는 레고 조각의 길이 ℓ이 주어진다. ℓ은 양의 정수이며, 단위는 나노미터이다. 블록의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.

출력

---

각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2)

정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.

 

문제 풀이

---

이분 탐색 문제.

구멍의 너비가 x이고 막으려고 시도하는 조각의 길이가 i라면, x - i의 길이를 가진 조각이 있는지 확인해주면 된다.

algorithm 헤더에 있는 binary_search() 함수를 이용하면 배열 혹은 벡터에 원하는 값이 있는지 확인할 수 있다. 탐색을 위해 정렬하고 순차적으로 탐색할 것이므로 이분 탐색의 범위는 현재 선택한 조각이 i번째라면 i+1번부터 끝까지만 확인해주면 된다.

혹은 투포인터로도 구현 가능하다. 

 

이 문제에는 테스트 케이스의 개수가 주어져 있지 않은데, cin.eof()를 사용하면 입력이 끝인지를 확인할 수 있다. while()문 안에서 반복적으로 테스트케이스를 입력받다, 입력 값이 eof라면 반복문을 빠져나가도록 구현한다.

 

아래는 코드.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	while (true)
	{
		int X, N;
		cin >> X;
		if (cin.eof())
		{
			break;
		}
		cin >> N;
		int* arr = new int[N];
		for (int i = 0; i < N; i++)
		{
			cin >> arr[i];
		}
		sort(arr, arr + N);
		long long length = 10000000 * X;
		bool canMake = false;
		for (int i = 0; i < N; i++)
		{
			if (binary_search(arr + i + 1, arr + N, length - arr[i]) == true)
			{
				cout << "yes " << arr[i] << " " << length - arr[i] << "\n";
				canMake = true;
				break;
			}
		}
		if (canMake == false)
		{
			cout << "danger" << "\n";
		}
	}

	return 0;
}