음.. 이 문제는 다들 이분매칭으로 푸는 것 같은데

일반적인 경우에 1000^3이 시간초과가 나지 않나요?

일반적으로 이분매칭의 시간복잡도가 O(Ef)고, 다음과 같은 데이터에서는 E ~ V^2, f~V가 되어 시간이 초과되어야 할 것 같습니다.

실제로 제 AC된 소스에서도 이 데이터는 Release모드로 10초 가까이 걸리더군요..

1000

1 1 1

2 2 2

....

1000 1000 1000

이런 문제가 있어 N제한을 줄이고 데이터를 보강할 필요가 있지 않을까 합니다.

최악의 경우 O(N^3) 알고리즘이 N = 1000인데도 0ms에 나오는거에 좀 놀랐습니다.