[BOJ 7573] 완전탐색2 - 고기잡이

처음에 N*N을 구현하고 처음부터 완탐을 했었는데, 시간초과가 났다.
N<=10^4이라 당연한 결과였다.

효율적으로 가장 많은 물고기를 잡는 그물들을 특정해서 구현을 해야한다.
즉 그물의 길이 또는 물고기의 개수로 한정지을만한 조건을 구해야된다.

그물을 치는것에 영향을 받는 요소는
1. 그물을 치는것을 시작하는 위치
2. 그물의 모양

이 두가지 밖에 없다.

1번에 해당하는 조건을 축소시켜야 한다.
문제에 답이 될만한 조건은 특정물고기와 특정물고기의 교차점이다.
(물고기 i의 x좌표 물고기 j의 y좌표를 그물을 시작하는 기준으로 정한다)

이렇게되면 O(m^3)으로 시간초과를 해결할수 있다.

for (size_t i = 0; i < m; i++)
	{
		for (size_t j = 0; j < m; j++)
		{
			for (size_t k = 1; k < l; k++)
			{
				calc(f[i].x, f[j].y, k, l - k);
			}
		}
	}

문제를 첨보고 많이 해맸다. 결국 solv를 보고 풀었고, 다음에 꼭 다시 풀어봐야할 문제이다.