백준 3649 - 로봇 프로젝트

 

 

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 구멍의 너비가 주어지고 레고 블록의 길이가 주어질 때 레고 블록 2개를 활용하여 정확히 구멍의 너비와 일치하는 것 중 차이가 가장 많이 나는 블록 2개를 고르는 것이다.

 

해당 문제를 러프하게 풀어보면 2개의 레고 조합을 만들고 그 합이 구멍의 너비와 같은 것 중 차이가 많이 나는 조합을 고르면 된다.

하지만 해당 문제는 n이 최대 1000000이기 때문에 조합을 만들어 풀면 시간 초과가 발생할 것이다.

 

해당 문제를 풀기 위해서는 조합하는 시간을 줄일 필요가 있다.조합 시간을 줄이는 가장 좋은 방법은 블록을 고르는 개수를 보면 알기 쉽다.블록은 무조건 2개를 사용해야 하기 때문에 하나를 고르면 다른 하나는 자동으로 길이가 정해진다.예를 들어 1cm인 구멍의 너비를 막기 위해 1 나노미터짜리 블록을 골랐다면 다른 하나의 블록은 9999999 나노미터여야만 한다.따라서 블록을 길이순으로 정렬하여 하나씩 골랐을 때 다른 하나가 존재하는지 판단하면 된다.

즉 이진 탐색으로 조합 시간을 줄일 수 있는 것이다.

 

시간을 더 줄일 수 있는 방법은 길이순으로 정렬했기 때문에 하나의 블록을 골랐다면 그 블록보다 짧은 블록을 탐색할 필요가 없다.

int maxDiff = -1;
int left = N, right = N;
for (int i = 0; i < N; i++)
{
    auto pos = lower_bound(blocks.begin() + i + 1, blocks.end(), hole - blocks[i]) - blocks.begin();

    if (pos < N && blocks[pos] == hole - blocks[i])
    {
        if (blocks[pos] - blocks[i] > maxDiff)
        {
            maxDiff = blocks[pos] - blocks[i];
            left = i;
            right = pos;
        }
    }
}

이진 탐색(lower_bound)를 활용하여 탐색하면 그 요소보다 크거나 같은 요소를 찾기 때문에 정확히 일치하는지 한 번 더 검증해야 한다는 점을 유의해야 한다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
long long hole;
int N;

int main()
{
	INPUT_OPTIMIZE;

	while (cin >> hole)
	{
		cin >> N;
		vector<int> blocks(N);

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

		hole *= 10'000'000;

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

		int maxDiff = -1;
		int left = N, right = N;
		for (int i = 0; i < N; i++)
		{
			auto pos = lower_bound(blocks.begin() + i + 1, blocks.end(), hole - blocks[i]) - blocks.begin();

			if (pos < N && blocks[pos] == hole - blocks[i])
			{
				if (blocks[pos] - blocks[i] > maxDiff)
				{
					maxDiff = blocks[pos] - blocks[i];
					left = i;
					right = pos;
				}
			}
		}

		if (left == N && right == N)
		{
			cout << "danger\n";
		}
		else
		{
			cout << "yes " << blocks[left] << " " << blocks[right] << "\n";
		}
	}

	return 0;
}

---