백준 7573 - 고기잡이

문제 설명

한국인의 식단에서 생선은 매우 중요한 단백질 공급원이다. 반면, 지구 온난화로 인한 바닷물의 온도 상승, 그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고기의 수가 줄어들고 있다. 정부에서는 이 문제를 심각하게 생각하여, 물고기를 잡을 수 있는 곳과 여기서 고기잡이 배가 사용할 수 있는 그물의 폭에 제한을 두었다. 물고기는 바다 표면 근처에 살기 때문에, 그물의 높이는 중요하지 않다. 따라서 그물은 길이가 l인 직선으로 생각할 수 있고, 물고기를 잡을 때, 그물은 한 변의 길이가 1 이상 정수인 직사각형 모양으로 치게 된다. 예를 들어, l = 10이라면, 칠 수 있는 그물의 모양은 1×4, 2×3, 3×2, 4×1과 같이 4가지 형태의 직사각형이 된다.

고기를 잡을 수 있는 곳은 N×N 크기의 모눈종이 모양으로 되어 있다. 각 모눈에는 좌표가 주어지며, 가장 왼쪽 위 모눈이 (1,1)이고, 가장 오른쪽 아래 모눈이 (N,N)이다. 총 M 마리의 물고기가 서로 다른 모눈 위에 한 마리씩 살고 있으며, 물고기는 움직이지 않는다. 고기잡이 배는 한 모눈 위에 위치를 잡고 자신의 오른쪽과 아래쪽으로 그물을 친다. 일단 그물을 치면, 그물 안, 그리고 그물에 걸친 물고기들을 잡을 수 있다. 예를 들면, 다음 그림은 N = 7, l = 10 이고 M = 6 마리의 물고기가 (2,2), (2,4), (3,3), (5,6), (6,2), (7,4)에 살고 있을 때, (2,2)에 놓인 고기잡이 배가 2×3 모양으로 그물을 친 예를 보이고 있다. 이때 고기잡이 배는 총 3마리의 물고기를 잡을 수 있다. 고기를 잡을 수 있는 영역 밖으로 그물을 치는 경우는 없다.

고기를 잡을 수 있는 영역, 물고기의 위치, 그물의 폭이 주어졌을 때 한 번의 그물치기로 잡을 수 있는 가장 많은 물고기의 마릿수를 구하는 프로그램을 작성하시오.

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

 

 

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 이차원 배열에 물고기가 임의로 들어가 있을 때, 둘레 L의 그물망을 이용하여 최대한 많은 물고기를 잡는 것이다.

 

처음에는 이차원 누적합을 이용하면 된다고 생각했다.

물고기의 수로 누적합을 만들고 그물의 가로, 세로가 (x, y) 이고 (i, j)번째 칸에서 시작하였을 때 누적합을 이용하면 시간 안에 문제를 풀 수 있다고 생각했다.

하지만, 메모리 초과가 발생했다.

int타입의 이차원 배열도 사용하지 못하는 꽤나 빡빡한 메모리 요구사항이 있었다.

(하지만 확인해 보니 char타입은 가능했다.)

 

따라서, 다른 접근법이 필요했다.

최대한 많은 물고기를 잡기 위해서는 그물의 시작점에 물고기가 위치하는 것이 제일 유리하다.

그래야 최대한 멀리까지 그물을 보낼 수 있기 때문이다.

즉, 물고기 시작점에서 그물의 가로, 세로를 가능한 조합을 만들어 던져본다면 정답을 구할 수 있다.

하지만, 예외가 존재한다.

물고기 시작점에서 그물을 던질 때, 범위를 넘어가버리면 그물을 던지지 못하는 경우가 생긴다.

이러한 경우에는 물고기 시작점에서 던진다는 것이 불가능해진다.

이를 해결하기 위해 그물을 w만큼 왼쪽으로 밀어 본다.

즉, 물고기가 그물의 상단에는 걸려 있으면서 왼쪽까지 최대한 미는 과정의 물고기 수를 구하는 것이다.

단, 물고기는 (y, x)를 기준으로 정렬되어 있어야 한다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N, L, M;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);

    cin >> N >> L >> M;

    vector<pair<int, int>> fishes;
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        fishes.push_back({ a,b });
    }

    sort(fishes.begin(), fishes.end());

    int ans = 0;
    //w: 가로
    for (int w = 1; w < L / 2; w++)
    {
    	//세로
        int h = L / 2 - w;
		
        if (w > N - 1 || h > N - 1) continue;
        for (int f = 0; f < M; f++)
        {
            auto [fishY, fishX] = fishes[f];
			
            //왼쪽으로 밀기
            for (int k = 0; k <= w; k++)
            {
                int cnt = 1;
				
                //범위 체크
                if (fishX - k < 1) break;
                for (int nextFish = f + 1; nextFish < M; nextFish++)
                {
                    auto [nextY, nextX] = fishes[nextFish];

                    if (nextY > fishY + h) break;
                    if (fishX-k <= nextX && nextX <= fishX+w-k) cnt++;
                }

                ans = max(ans, cnt);
            }
        }
    }

    cout << ans;

    return 0;
}

---