백준 14658번 - 하늘에서 별똥별이 빗발친다. (C++)

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

14658번: 하늘에서 별똥별이 빗발친다

 

문제조건

- 별똥별의 좌표가 주어지고 천을 펼쳤을 때 최대한 좌표가 천에 포함되어야한다.

 

내 접근

- 일단 N,M이 50만이라 절~~~대 O(N * M)으로는 풀어낼 수 없다. 그런데 아무리 봐도 문제가 브루트포스가 아니면 풀수가 없다고 생각됐다. 그래서 일단 풀 수 있는대로 해보니 당연히 시간초과가 났다. 어떻게 풀어야하나 고민하던 중 K는 100밖에 안되어서 고려해보니 각 K점을 꼭짓점으로 하고 1,2,3,4분면을 모두 확인하면 될 것이라 생각했다. 그러나 

 

   *

*    *

   *

 

이 반례를 해결할 수 없다.

 

올바른 풀이

- 그러므로 이 문제는 각 별의 x좌표와 다른 점의 y좌표를 점으로 두고 1사분면씩을 확인하는 것이다. 위의 예제를 확인해보자.

0,2  2,2  2,2

0,1   1,1   2,1

0,0  1,0  2,0  

 

에서 십자가로 별이 있다고 가정하면 각 별을 한 꼭짓점으로 해서는 풀 수 없다. 그러므로 각 별의 x좌표와 다른 별의 y좌표를 가져오는 것이다. 즉 x축에 무조건 하나의 별이 있고 y축에도 적어도 하나의 별이 무조건 있는 상황을 만드는 것이다. 

이렇게되면 위의 예제도 0,0을 기준으로 탐색을 하게 되므로 풀어낼 수 있다. 그렇다면 다른 상황은? 일반적으론 꼭짓점으로 하는 것이 답인 경우가 많다. 이때는 0,1 본인도 1사분면을 확인하기 때문에 걱정할 필요가 없다. 그렇다면 1사분면만 해결하면 되는걸까? 2,3,4 분면에도 답이 존재할 수 있지 않을까? 그럴수도 있다. 그러나 그 상황은 적어도 각 모서리에 한개의 별똥별이 존재하게 되는 이 방법의 전재조건에 걸린다. 그러므로 증명이 되어있다.

 

느낀점

- 브루트포스가 맞는데 너무 크다면 다른 관점으로 생각해보자. 그리고 이 문제를 처음 풀어보고서는 혼자힘으로 풀이하긴 힘들것 같다. 모르면 맞아야지 수준,,,,, 백준은 역시 많이 풀고 생각을 많이해야한다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int>> points;

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

	int N, M, L, K;
	cin >> N >> M >> L >> K;

	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		points.push_back({ x, y });
	}
	
	int dx1[] = {-1, 0, -1, 0};
	int dy1[] = {0, 0, -1, -1};
	int dx2[] = {0, 1, 0, 1};
	int dy2[] = {1, 1, 0, 0};
	
	int answer = -1;
	
	for(int i = 0; i < K; i++){
	    for(int j = 0; j < K; j++){
	        int x = points[i].first;
	        int y = points[j].second;
	        int ans = 0;
	        for(int k = 0; k < K; k++){
	            int px = points[k].first;
	            int py = points[k].second;
	            if (x <= px && y <= py && x + L >= px && y + L >= py) {
					//cout << "체킹 " << px << " ," << py << endl;
					ans++;
				}
	        }
	        answer = max(answer, ans);
	    }
	}
	
	cout << K - answer << '\n';
}