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

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

 

난이도 : 골드 3 
알고리즘 유형 : 브루트포스, 완전탐색 
풀이 시간 : 1시간 3분 

문제 풀이 

욱제는 커다란 네모난 $L * L$ 크기의 트램펄린을 준비했다. 이 트램펄린을 사용하여 최대한 많은 별똥별을 튕겨낼 때, 지구에 부딪히는 별똥별의 최소 개수를 구하자.

 

문제의 조건을 먼저 살펴보면, 지구의 크기를 나타내는 $0 ≤ N, M ≤ 500000$, 트램펄린의 크기를 나타내는 $1 ≤ L ≤ 100000$이 주어진다. 모든 지구를 탐색하는 방법을 사용한다면, 최악의 경우, $O(n^2)$로 시간초과가 날 것이다. 

문제에서는 별똥별의 개수도 주어졌다($1 ≤ K ≤ 100$). 별똥별의 위치 정보를 활용한다면 조건 안에 문제를 해결할 수 있을 것이다.

 

다음 문제는, 어떻게 별똥별의 크기에 맞는 트램펄린을 찾을 것인가? 이다.

 

먼저 별똥별 하나의 좌표를 중심으로 4방면을 확인해보는 방법이다.

이렇게 4방면으로 나눠서 확인하는 방법이 있다.

하지만, 이  방법을 사용한다면, 아래와 같은 경우에 최적의 값을 보장하지 못한다. 

빨간 점 : 별똥별 위치

다음과 같은 상황에서 L의 크기가 3인 경우에 위 방법을 사용한다면, 3개의 별똥별만 튕겨내게 된다.

 

따라서 우리는 두 별똥별의 위치를 기준으로 삼는 군집을 형성해야 한다. 

두 별똥별의 좌상단 좌표인 파란색 점을 기준으로 삼자

만약 L = 3인 경우, 모든 별똥별을 받을 수 있다.

위 그림을 보면, 빨간 네모로 표시한 두 별똥별이 포함되는 좌상단 좌표는 파란색 점이 될 것이고, 파란색 점 기준으로 트램펄린을 펼친다면 모든 별똥별을 담을 수 있다. 

좌상단 좌표를 구하는 방법은 선택한 두 별똥별의 row와 col 값을 비교하여 최솟값을 선택하면 된다. 

이후, 모든 별똥별에 대해 한 번 더 체크해가며 트램펄린의 범위 안에 들어오는지 체크하면 된다.

 

전체 시간복잡도는 for문을 총 3번 반복하기 때문에 $O(K^3) = O(100^3)$이 소요된다.

 

코드

/*
지표면에 떨어지는 별똥별의 수를 최소화하자!
네모난 L x L 크기의 트램펄린을 준비. 
별똥별이 어디로 떨어질 지는 이미 알고있다.
최대한 많은 별똥별을 튕겨내도록 트램펄린을 배치했을 때, 지구에는 몇 개의 별똥별이 부딪히게될까
- 별똥별은 트램펄린 모서리에 부딪혀도 튕겨나간다.

n, m <= 500000
풀이 : 만약, n, m이 50만이고 l이 1이라면, 2중 for문 돌 경우 시간초과난다. 50만 x 50만
단순한 브루트포스로는 풀이 불가능

군집을 찾아야한다 ?
두 개의 별똥별은 선택한 다음, 그 두 별똥별의 공통된 좌상단 좌표를 찾기
찾은다음, 별똥별 세기
*/

#include <iostream>
#include <algorithm>
#include <vector>
#define INIT cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;

int n, m, l, k;

int main() {
	INIT;
	cin >> n >> m >> l >> k;
	vector<pair<int, int>> stars(k);
	for (int i = 0; i < k; i++)
		cin >> stars[i].first >> stars[i].second;

	int ans = k;
	// 두 꼭짓점이 교차하는 좌상단 좌표 먼저 찾기 
	for (int i = 0; i < k; i++) {
		for (int j=0;j<k;j++){
			int r = min(stars[i].first, stars[j].first);
			int c = min(stars[i].second, stars[j].second);
			// 찾은 좌표에서 l만큼 범위 안에 속하는 별똥별 찾기
			int tmp = 0;
			for (auto star : stars) {
				if (r <= star.first && star.first <= r + l && c <= star.second && star.second <= c + l)
					tmp++;
			}
			ans = min(ans, k - tmp);
		}
	}

	cout << ans << '\n';

	return 0;
}

배운 점 

어제 코딩테스트와 관련된 한 영상을 보았는데, 문제를 풀기 전에 어떤 알고리즘을 사용하고, 시간복잡도 및 공간복잡도를 사전에 확인하라는 말을 들었다.

이 과정이 키보드에 손을 올리기 전에 꼭 생각해야 할 점이라고 생각하며 마음속에 새겨야 할 것이다.