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

 이 문제는 완전 탐색 문제임을 판단하는 것이 중요하다. 가로와 세로의 길이가 각각 최대 500000이기 때문에, 이차원 배열을 만들 수 없다. 하지만 별똥별의 개수가 최대 100개이므로 나올 수 있는 좌표의 최대 가짓수는 100 * 100 = 10000 이고, 트램펄린을 설정한 뒤 이 안에 들어있지 않은 별똥별의 개수를 세는 것 또한 100번이 들기 때문에 1000000 번의 연산이면 가능하다. k를 이용한 완전 탐색을 수행해야한다는 것까지는 생각해냈지만, 좌표의 모든 가짓수로 트램펄린을 좌상단으로 설정하는 것은 생각하지 못해 아쉬운 문제였다. 또한 트램펄린의 모서리까지도 튕겨낸다는 것은 endY가 startY + l이 됨을 의미하는 것도 생각하지 못했다.

 

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

vector<pair<int, int>> stars;

int n, m, l, k;

bool inRange(int startY, int endY, int startX, int endX, int y, int x)
{
	if (startY <= y && y <= endY && startX <= x && x <= endX)
	{
		return true;
	}
	return false;
}

int func(int startY, int startX)
{
	int endY = startY + l;
	int endX = startX + l;
	int result = 0;

	for (int i = 0; i < stars.size(); i++)
	{
		int x = stars[i].first;
		int y = stars[i].second;

		if (!inRange(startY, endY, startX, endX, y, x))
		{
			result++;
		}
	}

	return result;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> l >> k;

	for (int i = 0; i < k; i++)
	{
		int x, y;

		cin >> x >> y;

		stars.push_back(make_pair(x, y));
	}

	int result = k;

	for (int i = 0; i < stars.size(); i++)
	{
		int x = stars[i].first;

		for (int j = 0; j < stars.size(); j++)
		{
			int y = stars[j].second;

			result = min(result, func(y, x));
		}
	}

	cout << result << '\n';

	return 0;
}