[G3] 백준 14658번 하늘에서 별똥별이 빗발친다 C++ set, 브루트포스 알고리즘

리뷰

 

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

50만 * 50만 맵에서 L * L크기의 범위에 최대한 많은 별을 넣는 문제

 

전역 변수

• n, m : 맵의 x좌표의 크기 n, y좌표의 크기 m
• l : 별을 담기 위한 정사각형의 한 변의 길이
• k : 주어지는 별똥별의 개수
• ans : 정답을 출력하기 위한 변수, 최대한 큰 값으로 설정한다.
• Star : 주어진 별똥별 x, y좌표 정보를 저장하기 위한 구조체
• xdic : 별똥별의 x좌표를 저장하기 위한 set
• ydic : 별똥별의 y좌표를 저장하기 위한 set

 

함수

없음

 

 

문제풀이

1. n, m, l, k 값을 입력 받고, Star구조체 벡터 stars를 초기화 해준다.
2. 별똥별의 개수 k개를 입력 받고, stars구조체에 넣어준다, 이때 x, y좌표를 각각 xdic, ydic에 insert해준다.
3. xdic을 순회하고, 내부에서 ydic을 순회 해준다.
4. nx, ny는 각각 x + l, y + l로 초기화 해준다.
5. cnt를 0으로 초기화 해주고, 별똥별 정보가 담긴 벡터 stars를 초기화 해준다.
6. 만약 별똥별의 x, y좌표가 x ~ nx, y ~ ny내부에 포함한다면 cnt를 증가시켜준다.
7. ans를 k - cnt와 비교하여 최소값을 갱신해 준다.
8. 모든 탐색을 마친 뒤 ans에 저장된 값을 출력해 준다.

 

참고 사항

• 주어지는 별똥별의 개수 k가 최대 100개이므로 최악의 케이스일 경우 100 * 100 * 100만에 연산이 가능하다.
• x -> y순으로 탐색했을 경우 y가 끝난 시점마다 ans를 초기화 해주어야 한다.

 

정답 코드

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

int n, m, l, k, ans = 1e9;

struct Star {
	int x, y;
};

set<int> xdic;
set<int> ydic;

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

	cin >> n >> m >> l >> k;
	vector<Star> stars;
	for (int i = 0; i < k; i++) {
		int x, y; cin >> x >> y;
		stars.push_back({ x, y });
		xdic.insert(x);
		ydic.insert(y);
	}

	for (int x : xdic) {
		for (int y : ydic) {
			int nx = x + l, ny = y + l;
			int cnt = 0;
			for (const Star& star : stars) {
				if (x <= star.x && star.x <= nx && y <= star.y && star.y <= ny) cnt++;
			}
			ans = min(ans, k - cnt);
		}
	}
	cout << ans;
}