[백준/BOJ] 백준 14658번 : 하늘에서 별똥별이 빗발친다

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

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

 

지표면에 떨어지는 별똥별의 수를 최소화하기 위해, 트램펄린 모서리에 별이 위치해야, 많은 별을 튕겨낼 수 있다. 이를 위해, 별을 많이 튕겨낼 수 있는 경우인, 기존 별의 위치와 별 사이의 교차 지점을 기준으로 트램펄린을 펼치는 방법으로 문제를 해결했다.

 

코드

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

int n, m, l, k;
vector<pair<int, int>> star;
vector<pair<int, int>> point; //두 별 사이 교차점

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

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

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

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

	//트램펄린의 모서리에 별이 위치할 수록 유리하기 때문에, 최적의 답을 만들 수 있는 경우인 기존 별의 위치와 별 사이의 교차 지점을 기준으로 트램펄린을 펼친다
	//기존 별의 위치와 별 사이의 교차 지점을 point에 저장한다
	for (int i = 0; i < star.size(); i++) {
		point.push_back(star[i]);
		for (int j = i + 1; j < star.size(); j++) {
			point.push_back(make_pair(star[i].first, star[j].second));
			point.push_back(make_pair(star[j].first, star[i].second));
		}
	}

	//기존 별의 위치와 별 사이의 교차 지점을 기준으로 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래로 트램펄린을 배치하는 경우 확인
	int max_cnt = 0;
	for (int i = 0; i < point.size(); i++) {

		vector<int> cnt(4, 0);

		for (int j = 0; j < star.size(); j++) {
			//해당 point를 기준 왼쪽위
			if ((star[j].first >= point[i].first - l && star[j].first <= point[i].first) && (star[j].second >= point[i].second - l && star[j].second <= point[i].second)) {
				cnt[0]++;
			}

			//해당 point를 기준 오른쪽위
			if ((star[j].first >= point[i].first - l && star[j].first <= point[i].first) && (star[j].second >= point[i].second && star[j].second <= point[i].second + l)) {
				cnt[1]++;
			}

			//해당 point를 기준 왼쪽아래
			if ((star[j].first >= point[i].first && star[j].first <= point[i].first + l) && (star[j].second >= point[i].second - l && star[j].second <= point[i].second)) {
				cnt[2]++;
			}

			//해당 point를 기준 오른쪽아래
			if ((star[j].first >= point[i].first && star[j].first <= point[i].first + l) && (star[j].second >= point[i].second && star[j].second <= point[i].second + l)) {
				cnt[3]++;
			}
		}

		int temp_max_cnt = max(max(cnt[0], cnt[1]), max(cnt[2], cnt[3]));
		max_cnt = max(max_cnt, temp_max_cnt);
	}

	int result = star.size() - max_cnt;
	cout << result;

	return 0;
}