[백준] 하늘에서 별똥별이 빗발친다. (C++)

출처 : https://www.acmicpc.net/problem/14658

 

풀이 방법

 

완전 탐색의 기본 아이디어

• 이 문제는 완전 탐색으로 해결해야 한다.

• 다만, 보드를 전체적으로 탐색하면 시간 초과가 발생하므로 별똥별 좌표를 기준으로 탐색을 진행한다.

 

 

사각형(트램펄린) 위치 설정 시 주의점

• 별똥별을 기준으로 탐색하더라도, 어떻게 트램펄린 사각형을 위치시키는지가 핵심이다.

• 특정 별똥별을 사각형의 꼭짓점에만 맞추는 방식으로는 최적해를 놓칠 수 있음을 주의한다.

 

 

그러므로 위의 예시에서도 힌트가 되었지만, 정답은 최소 2점이 각 변이나 꼭짓점에 있는 경우가 정답이 된다.

이게 왜 그런지 증명을 해보도록 하겠다.

예를 아래와 같이 점 세개가 트램펄린 안에 있는 경우 아래와 같은 사각형도 정답이 될 수 있다.

하지만 해당 사각형을 최대한 점에 붙게 이동시켜 점이 각 변에 위치하는 경우도 정답이 된다.

 

 

즉 여러개의 정답이 있지만 여러 정답 중 두 점이 변이나 꼭짓점에 있도록 사각형을 이동시킨 트램펄린을 만든 후 해당 트램펄린만 계산할 생각이다.

 

해당 사각형을 만들기 위해선 이중 for문을 통해 2 점을 정한 후 한 점을 x축으로 한 점을 y축으로 사용해 사각형만들 생각이다.

 

이렇게 하게 된다면 갑자기 의문점이 생길 수 있다. 만약 트램펄린의 길이 L보다 멀리 떨어진 두 점이라면 위 방법으로 사각형을 만들게 된다면, 두 점이 포함이 안될 수 도 있는데?라는 생각이 든다. (아래 예시 참고)

하지만 위의 경우 해당 사각형이 정답이 될 가능성이 없기 때문에, 제거를 하고 탐색하지 않고 포함 시켜서 탐색을 진행했다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, l, k;
vector<pair<int, int>> stone;
int answer = 0;

void sol() {
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < k; j++) { // 모두 탐색
			int x = stone[i].second;
			int y = stone[j].first;
			int cnt = 0;

			for (int z = 0; z < k; z++) {
				if (x <= stone[z].second && stone[z].second <= x + l && y <= stone[z].first && stone[z].first <= y + l) cnt++;
			}
			answer = max(cnt, answer);
		}
	}
}

int main() {

	cin >> n >> m >> l >> k;
	int a, b;
	for (int i = 0; i < k; i++) {
		cin >> a >> b;
		stone.push_back(make_pair(a, b));
	}
	sol();
	cout << k - answer;
	return 0;
}