처음에 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를 보고 풀었고, 다음에 꼭 다시 풀어봐야할 문제이다.
