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

풀이 방법 : 브루트 포스

우리가 배치한 트램펄린의 범위 안에 들어오는 별똥별의 갯수를 세줘서 그 최댓값을 구하면 된다.

처음에는 각 별똥별의 좌표가 트램펄린의 가장자리에 오는 경우만 생각해도 될 거라 생각했는데 예외가 너무 많았다.
입력되는 별똥별 갯수의 최댓값이 100개로 매우 적기도 하고 가능한 모든 경우를 탐색하는 것이 맞다고 생각했다.

그래서 별똥별의 원래 좌표와(X,Y), X,Y값을 각 배열에 따로 저장해주고 X, Y 각 배열들을 오름차순으로 정렬해줬다.
그 후 이중 for 문 돌려주면서 X, Y 좌표가 트램펄린의 시작점일 때 팅겨낼 수 있는 별똥별의 갯수를 세주면서 최댓값을 갱신해나갔다.

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

using namespace std;

int N, M, L, K;

int Max = 0;

//별똥별의 갯수 세주기
int Check(int StartX, int StartY,int EndX, int EndY
, const vector<pair<int, int>>& vecPos)
{
	int Cnt = 0;

	for (int i = 0; i < K; ++i)
	{
		if (vecPos[i].first <= EndX &&
			vecPos[i].first >= StartX &&
			vecPos[i].second <= EndY &&
			vecPos[i].second >= StartY)
			++Cnt;
	}

	return Cnt;
}

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	cin >> N >> M >> L >> K;

	vector<int> vecX;
	vector<int> vecY;
	vector<pair<int, int>> vecPos(K);

	for (int i = 0; i < K; ++i)
	{
		cin >> vecPos[i].first >> vecPos[i].second;

		vecX.push_back(vecPos[i].first);
		vecY.push_back(vecPos[i].second);
	}

	sort(vecX.begin(), vecX.end());
	sort(vecY.begin(), vecY.end());

	for (int i = 0; i < K; ++i)
	{
		for (int j = 0; j < K; ++j)
		{
			Max = max(Max, Check(vecX[i],vecY[j], vecX[i] + L, vecY[j] + L, vecPos));
		}
	}

	cout << K - Max;
	
}