백준 7573: 고기잡이

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

 

일단 나는 단순하게 생각을 했다. 물고기 위치를 하나 잡아서 꼭짓점으로 잡아서 각각 1,2,3,4 분면을 길이를 조정하는 방식을 하면 쉽게 해결할 수 있을것이라 생각했다.

#include <iostream>
#include <algorithm>
using namespace std;
pair<int, int> P[101];
int N, L, M, ans = 0;
int dy[4] = { -1, 1, -1, 1 };
int dx[4] = { 1, -1, -1, 1 };
bool inRange(int y, int x)
{
	return y >= 1 && x >= 1 && y <= N && x <= N;
}
bool cmp(int sy, int sx, int ey, int ex, int idx)
{
	if (sy > ey) return cmp(ey, sx, sy, ex, idx);
	if (sx > ex) return cmp(sy, ex, ey, sx, idx);
	return (P[idx].first >= sy && P[idx].second >= sx && P[idx].first <= ey && P[idx].second <= ex);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> L >> M;
	for (int i = 0; i < M; i++) cin >> P[i].first >> P[i].second;
	L /= 2;
	for (int idx = 0; idx < M; idx++)
	{
		for (int d = 0; d < 4; d++)
			for (int w = 1; w < L; w++)
			{
				int sy = P[idx].first;
				int sx = P[idx].second;
				int ey = sy + dy[d] * w;
				int ex = sx + dx[d] * (L - w);
				if (ey > N)
				{
					sy -= (ey - N);
					ey = N;
				}
				if (ex > N)
				{
					sx -= (ex - N);
					ex = N;
				}
				if (ey < 1)
				{
					sy -= ey;
					ey = 1;
				}
				if (ex < 1)
				{
					sx -= ex;
					ex = 1;
				}
				if (!inRange(sy, sx)) continue;
				int cnt = 0;
				for (int i = 0; i < M; i++)
					cnt += cmp(sy, sx, ey, ex, i);
				ans = max(ans, cnt);
			}
	}
	cout << ans << '\n';
}

그물 위치가 밖을 넘는 것을 우려해 조정까지 했다. 하지만 내가 마주한 건 "틀렸습니다"였다.

 

결국 문제의 해결책이 떠오르지 않은 나는 구글링을 했다.

https://dleunji.tistory.com/205

[백준] 7573번: 고기잡이

간단히 말해서, 물고기 2개를 위치를 기준으로 그물 길이를 조정하며 그 사이에 있는 물고기 갯수를 세어 정답과 비교하면 된다.

그렇게 문제를 해결했는데...

#include <iostream>
#include <algorithm>
using namespace std;
int N, L, M, ans = 0, X[101], Y[101];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> L >> M;
	for (int i = 0; i < M; i++) cin >> X[i] >> Y[i];
	for(int x = 0; x < M; x++)
		for(int y = 0; y < M; y++)
			for (int l = 1; l < (L / 2); l++)
			{
				int nx = X[x] + l;
				int ny = Y[y] + (L / 2) - l;
				int cnt = 0;
				for (int idx = 0; idx < M; idx++)
					cnt += (X[idx] <= nx && Y[idx] <= ny && X[idx] >= X[x] && Y[idx] >= Y[y]);
				ans = max(ans, cnt);
			}
	cout << ans << '\n';
}

해결한 건 좋은데, 나는 이것과 비슷한 문제를 예전에 스스로 해결한 적이 있다는 것을 깨달았다.

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

 

이 문제는 이번에 다룬 문제와 유사하게 해결할 수 있는데. 문제점은 나는 이 문제를 거의 2년전에 구글링 없이 스스로 해결했다는 것이다. 즉, 나는 이 문제를 스스로 해결할 수 있었는데, 조금 귀찮다는 이유로 구글링으로 답을 구한게 안타깝다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;
int N, M, K, L, ans = 0;
vector<pii> SS;
vector<int> X, Y;
int dx1[4] = { 0, -1, -1, 0 };
int dy1[4] = { 0, 0, -1, -1 };
int dx2[4] = { 1, 0, 0, 1 };
int dy2[4] = { 1, 1, 0, 0 };
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> L >> K;
	SS.resize(K);
	for (int i = 0; i < K; i++)
	{
		cin >> SS[i].first >> SS[i].second;
		X.push_back(SS[i].first);
		Y.push_back(SS[i].second);
	}
	for (int i = 0; i < K; i++)
		for (int j = 0; j < K; j++)
			for (int d = 0; d < 4; d++)
			{
				int cnt = 0;
				int X1 = X[i] + dx1[d] * L;
				int Y1 = Y[j] + dy1[d] * L;
				int X2 = X[i] + dx2[d] * L;
				int Y2 = Y[j] + dy2[d] * L;
				for (int idx = 0; idx < K; idx++)
					if (X1 <= SS[idx].first && X2 >= SS[idx].first && Y1 <= SS[idx].second && Y2 >= SS[idx].second)
						cnt++;
				ans = max(ans, cnt);
			}
	cout << (K - ans) << '\n';
}

비록 해결한지 좀 된 문제일지언정, 스스로 해결한 문제도 이렇게 막혀서야, 매일 문제를 푸는 보람이 없다... 전에 푼 문제도 점검해보는 시간을 가져보는 것도 괜찮을거 같다.