[백준/BOJ] 백준 7573번 : 고기잡이

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

7573번: 고기잡이

 

각 물고기를 기준으로, 해당 물고기가 그물에 걸리는 모든 경우의 수를 확인하여, 해당 경우에서 총 물고기가 몇 마리 걸리는지 확인하여, 물고기가 가장 많이 걸리는 최댓값을 구해서 문제를 해결했다.

 

코드

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

int n, l, m;
vector<pair<int, int>> fish;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> l >> m;

	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;

		fish.push_back(make_pair(x, y));
	}

	int result = 0;
	for (int i = 0; i < m; i++) {
		//i번째 물고기가 그물에 걸리도록 그물을 펼친다

		//그물이 펼쳐질 수 있는 경우를 모두 확인한다
		//aa:그물 직사각형의 세로 길이 * 2, bb:그물 직사각형의 가로 길이 * 2
		for (int aa = 1; aa <= l - 1; aa++) {
			int bb = l - aa;

			if ((aa % 2 == 1) || (bb % 2 == 1)) {
				continue;
			}

			int a = aa / 2;
			int b = bb / 2;

			//i번째 물고기가 그물에 걸리도록 그물을 펼치는 모든 경우를 확인
			for (int x = fish[i].first - a; x <= fish[i].first + a; x++) {
				for (int y = fish[i].second - b; y <= fish[i].second + b; y++) {
					pair<int, int> point = make_pair(x, y); //point위치에서 그물을 펼칠때

					//해당 그물이 영역을 벗어날 때
					if (point.first <= 0 || point.second <= 0) {
						continue;
					}
					if (point.first + a > n || point.second + b > n) {
						continue;
					}

					int temp_result = 0;
					for (int j = i; j < m; j++) { //j를 i부터 확인하는 이유는, 그 이전꺼(i-1 이하)는 이미 해당 위치가 그물에 걸리는 경우를 모두 확인했다
						if ((fish[j].first >= point.first) && (fish[j].first <= point.first + a) && (fish[j].second >= point.second) && (fish[j].second <= point.second + b)) {
							temp_result++;
						}
					}
					result = max(result, temp_result);
				}
			}
		}
	}

	cout << result;

	return 0;
}