취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 7573번 문제인 고기잡이이다.
문제는 아래 링크를 확인하자.

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

어떤 그물을 쳐서 그 그물에 걸리는 물고기의 수가 최대일 때, 항상 이 그물을 평행이동시켜 원래 잡을 수 있던 모든 물고기가 들어있으면서 (문제에 주어진 그림 기준으로) 왼쪽변에서 잡히는 물고기가 있게끔 옮길 수 있다.

따라서, 모든 물고기(M마리)에 대하여, 이 물고기를 왼쪽변 위에 있게 하면서 그물을 펼치는 모든 경우의 수(O(l^2))만큼 그물을 펼쳐 그 안에 몇 마리의 물고기가 들어있는지 각 M마리의 물고기에 대해 확인하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int ans = 0;
int N, l, M;

pair<int, int> fish[100];
vector<pair<int, int>> group;

void solve(int idx) {
	auto& p = fish[idx];
	group.clear();
	for (int i = 0; i < M; i++) {
		if (abs(fish[i].first - p.first) + abs(fish[i].second - p.second) <= l) group.emplace_back(fish[i]);
	}

	for (int x = 1; x < l; x++) { // x by y 박스
		int y = l - x;

		for (int dx = 0; dx <= x; dx++) {
			int tmp = 0;
			int xL = p.first - dx, xR = p.first + (x - dx);
			int yL = p.second, yR = p.second + y;
			for (auto pp : group) {
				if (xL <= pp.first && pp.first <= xR && yL <= pp.second && pp.second <= yR) tmp++;
			}
			ans = max(ans, tmp);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> l >> M; l >>= 1;
	for (int i = 0; i < M; i++) {
		cin >> fish[i].first >> fish[i].second;
	}

	for (int i = 0; i < M; i++) {
		solve(i);
	}

	cout << ans;
}