kks227   3달 전

각 플레이어마다 남은 경기를 재설정하여 그를 우승하게 만들 수 있는지 최대 유량을 구해 판별하는 방법을 사용하였는데

이 경우 플레이어 명수가 N일 때 정점 개수 O(N^2), 최대 유량 O(N^2)이므로 총 O(N^5)의 시간복잡도가 소모되고

N<=30이라 그래도 가능하긴 할 것 같아 제출했더니 테스트 케이스 개수가 100개라 그런지 시간초과가 나네요.

그래서 줄일 수 있는 방법이 있나 해서 정식 솔루션을 찾아봤더니 저렇게 하는 거라며 최종 시간복잡도가 O(N^5)가 맞다고 해서 당황스럽습니다.

어떻게 하면 시간초과가 안 날 수 있을까요? 별도의 최적화가 필요할까요?

깨작꺠작한 입력 시간이지만, 한 글자 단위 말고 한 줄 단위로 문자열 입력을 통해 입력받으면 조금 빨라질 듯하네요

그리고 문제의 특성상, 간선을 초기화하고 재사용하면 용량 0 이하인 유령 간선들이 존재해 BFS가 오래 걸릴 듯해요.

그러니 간선을 그냥 매번 다 삭제해버리고 네트워크를 rebuild하는 게 더 빠를것 같지만 그렇게 되면 상수 오더가 더 붙게 되니

이 부분은 확실히는 잘 모르겠네요.

그리고 103번 줄이 중괄호가 없어 101번 줄의 포문과 연결되어있지 않은데, 코딩 미스인 듯합니다.

또한 동점이어도 우승 가능합니다. 72번 줄의 수정이 필요해 보입니다.

76번 줄에서, w배열은 승수의 차이가 아닌 승점의 차이를 이미 담고 있는데 굳이 두 배를 한 것도 코딩 미스 같아요.

혹시 이런 코딩 미스들이 나비효과로 시간초과를 만들어버린 걸지도 모르니 수정해보세요

kks227   3달 전

음... 감사합니다. 한 줄 단위로 입력받기랑 용량이 0이 되는 간선 삭제는 아직 안해 봤는데, 여전히 시간 초과네요. 나중에 다시 해봐야겠습니다.

댓글을 작성하려면 로그인해야 합니다.