[BOJ/백준][Gold4] 7573 : 고기잡이 (C++)

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

7573번: 고기잡이

 

 

[난이도] Gold4
[유형] 브루트포스

[풀이]
N이 10^4라서 2차원 배열에 체크해놓고 뭘 할려고 하면 시간초과가 난다.

제한이 10^2인 L,M (그물의 둘레,고기들의 개수) 를 기준으로 문제를 풀어가야 한다.
모든 고기 i를 확인하면서 그 고기를 그물 끝에 걸리게 하는 모든 그물을 만들어서
i+1~M번째 고기들이 그물 안에 들어올 수 있는지를 확인하면 된다.

주의할점이 그물을 만들 때 i번 고기가 꼭지점에만 오도록 하면 안되고
좌우로 움직여주면서 i번 고기가 그물 끝에 걸릴 수 있는 모든 그물에 대해서
확인을 해줘야 한다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N,L,M,ans;
pair<int,int> v[10000];
int main(){
    scanf("%d%d%d",&N,&L,&M);
    for(int i=0;i<M;i++) scanf("%d%d",&v[i].first,&v[i].second);
    sort(v,v+M);
    for(int h=1;h<L/2;h++){
        int w = L/2-h;
        if(w>N-1||h>N-1) continue;
        for(int i=0;i<M;i++){
            int y = v[i].first,x=v[i].second;
            for(int k=0;k<=w;k++){
                int cnt=1;
                for(int j=i+1;j<M;j++){
                    int ny = v[j].first, nx=v[j].second;
                    if(ny>y+h) break;
                    if(x-k<=nx&&nx<=x-k+w) cnt++;      
                }
                ans = max(ans,cnt);
            }
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/7573.cpp