TLE가 발생하는 주 원인은 성격의 종류가 매우 다양한 경우(테스트 케이스 20, 테스트 케이스 23)입니다.
이를 개선할려면 O(N*T)에서 O(N*log T)으로 개선되어야 하나 어떤 방법으로 개선되어야 하는지 잘 모르겠습니다.
추가로 이 문제는 이분 매칭으로 뭔가 아이디어를 떠올리면 가능성이 보일 것 같은데 음...
+ 테스트 케이스 2에서 (3, 8) <-> (1, 2)가 확실히 최적해가 맞다는 정보를 미리 알고 있다면
3 10
4 2
1 5
1 3
여기서 (4, 2) <-> (1, 5)로 7이라는 최적해를 구하고, 그 다음 아까 미리 최적해를 구했던 (3, 8) <-> (1, 2)로 10을 구하여 7 + 10 = 17로 유도가 됩니다.
즉, 어떤 수많은 데이터가 존재하는 경우 매트로이드 등을 통하여 일부 데이터 쌍이 확실한 최적해를 보장 받을 수만 있다면 분할 정복 형식으로 해결할 가능성이 보입니다.
과연 그 방법은 무엇일까요?
+ 원본 그래프 + 복사 그래프로 이분 매칭 + 그리디 적용하여 구할려고 하는데 자꾸 일부 테스트 케이스에서 어긋난 경우가 많이 생겨납니다.
모든 테스트 케이스가 일치하고 TLE 안 뜨면 AC 판정 받을 수 있을 것 같은데 와... 이 문제 뭘까요?

kjk9704 1년 전 2
비록 아직 AC 판정을 받지 못 했으나 구현하는 과정에서 23가지 테스트 케이스가 등장하여 여기에 공유합니다.
Python(PyPy) 혹은 C++로 계속 도전하고 있긴 한데 자꾸 1% 혹은 7% 구간에서 틀리네요.