[BOJ] 7573 고기잡이

 

7573번: 고기잡이

단순한 방법으로 하면 4중 중첩이 된다. 당연히 시간초과가 난다.

 

물고기를 기준으로 for문을 돌려야 한다.

▶그물의 크기를 정하고 (sx, sy) 위치를 탐색할 때, 모든 지점을 탐색하면 TLE 발생

위와 같이 (4, 3)에서 그물을 치는 것은 비효율 적입니다.

▶ 어디를 (sx, sy)로 설정하는 것이 좋을까요?

물고기가 존재하는 위치 & 물고기간의 교차점

※ (2, 3)과 (4, 5)과 주어질 때 두 좌표의 교차점은  (4, 3)과 (2, 5) 입니다.

 

#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);
}

 

 

 

[BOJ] 백준 7573 고기잡이

 

백준7573 고기잡이