백준14658 하늘에서 별똥별이 빗발친다

작성일 | In

문제 링크

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

문제 출처

  • 제1회 천하제일 코딩대회 본선 I번

시간복잡도

  • O(k3)

풀이

백준-고기잡이(7573) 문제와 유사한 문제입니다.
완전 탐색은 시간 초과가 뜨기 때문에 버리고,
트램펄린에서 이웃한 모서리에 두 개의 별이 걸쳐지게 하는 방식으로 탐색하면 O(k^3)으로 해결 가능할 것 같습니다.

  1. 트램펄린에 튕겨져 나갈 별의 개수를 구하는 calc라는 함수를 만듭니다.
  2. n, m, l, k를 입력 받습니다.
  3. 별 위치를 입력 받습니다.
  4. 별 중에서 2개를 고른 후, 그 두 별이 트램펄린에서 이웃한 모서리에 걸쳐지게 트램펄린을 이동한 후, calc 함수로 계산합니다.
  5. 3번 항목을 k^2번 반복합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

struct star{
	int x, y;
};

int n, m, l, k, res;
vector<star> arr;

void calc(int x, int y){
	int cnt=0;
	for(int i=0; i<k; i++){
		if(x<=arr[i].x && arr[i].x<=x+l && y<=arr[i].y && arr[i].y<=y+l) cnt++;
		res = max(res, cnt);
	}
}

int main(){
	cin >> n >> m >> l >> k;
	arr.resize(k);
	int max = 0, maxx, maxy;

	for(int i=0; i<k; i++){
		cin >> arr[i].x >> arr[i].y;
	}

	for(int i=0; i<k; i++){
		for(int j=0; j<k; j++){
			calc(arr[i].x, arr[j].y);
		}
	}

	cout << k-res;
}