[백준] 7573번 고기잡이 (C++)

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

 

슬라이딩 윈도우같은 문제인데 사실은 브루트포스이다. 초등수준 도형 지식을 요구한다.

 

고기를 기점으로 왼쪽 사이드에 고기가 있다고 가정하고 브루트포스하면 되는 문제다.

 

단, 그물이 모든 바다를 덮을 수 있는 경우를 예외처리해야한다.

 

난 1만 * 1만 배열은 만들어 고기를 관리했는데 이렇게하면 메모리를 많이쓴다. 다른 사람들은 이렇게 안한것같다.

 

하지만 메인 로직은 같기 때문에 따로 참고하진 않았다. 

 

#include<iostream>
#include<vector>
#define MAX 10001
using namespace std;
int N, I, M;
bool sea[MAX][MAX];

vector<pair<int, int>> fishs(101);

int fishing(int n, int m, int x, int y){
    if(x < 1) return 0;

    int cnt = 0;

    for(int i = x; i <= x + n; i++){
        for(int j = y; j <= y + m; j++){
            if(i > N || j > N) return 0;
            if(sea[i][j] == 1) cnt++;
        }
    }

    return cnt;
}

int sol(int n, int m){
    int ans = 0;

    ans = max(ans, fishing(n, m, 1, 1));

    for(pair<int, int> p : fishs){
        for(int i = 0; i <= n; i++){
            ans = max(ans, fishing(n, m, p.first - i, p.second));
        }
    }

    return ans;
}

int main(){
    cin >> N >> I >> M;

    for(int i = 0; i < M; i++){
        cin >> fishs[i].first >> fishs[i].second;

        sea[fishs[i].first][fishs[i].second] = 1;
    }

    int answer = 0;

    for(int i = 1; i <= I; i++){
        for(int j = 1; j <= I; j++){
            if(i * 2 + j * 2 == I) {
                answer = max(answer, sol(i, j));
            }else if(i * 2 + j * 2 > I) break;
        }
    }

    cout << answer << '\n';
}