백준7573 고기잡이

작성일 | In

문제 링크

  • http://icpc.me/7573

문제 출처

  • 2013 지역 본선 중등2

시간복잡도

  • O(n3)

풀이

완전 탐색은 시간 초과가 뜨기 때문에 다른 방법을 찾아야 합니다.
그물에서 이웃한 모서리에 두 마리의 물고기가 걸쳐지게 하는 방식으로 탐색하면 O(m^3)으로 해결 가능할 것 같습니다.

  1. 그물에 걸릴 물고기의 수를 계산하는 calc라는 함수를 만듭니다.
  2. n, l, m을 입력 받습니다.
  3. 물고기의 위치를 입력 받습니다.
  4. 물고기 중에서 2개를 고른 후, 그 두 물고기가 그물에서 이웃한 모서리에 걸쳐지게 그물을 이동한 후, calc 함수로 계산합니다.
  5. 3번 항목을 m^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 pos{
	int x, y;
};

int n, m, l, res=0;
vector<pos>arr;

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

int main(){
	scanf("%d %d %d", &n, &l, &m);
	for(int i=0; i<m; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		arr.push_back({x, y});
	}
	for(int i=0; i<m; i++){
		for(int j=0; j<m; j++){
			for(int k=1; k<l/2; k++){
				calc(arr[i].x, arr[j].y, k, l/2-k);
			}
		}
	}
	printf("%d", res);
}