wldnjs3633   1년 전

백트래킹 DFS로 문제 풀이를 했는데요

처음 틀렸을때 시간초과가 나서 두 팀 스코어의 차이만 구하면 되니 멤버를 뽑는 순이 오름차순에 중복이 안되는 걸로 구했는데요

그래도 시간초과로 나오더라고요...

이걸 어떻게 해결해야 하는지 모르겠는데 부탁드릴게요ㅠㅠㅠㅠㅠㅠ

kokodak   1년 전

아마 backtracking 함수 안에 있는 2중 for문 때문인 것 같습니다. 사실 매번 백트래킹 함수를 호출할 때마다 O(N^2)으로 스타트팀과 링크팀을 뽑기보다는, O(N)으로 스타트팀을 먼저 뽑아낸 후에, 스타트팀에서 뽑은 인원이 sizenum / 2이 됐을 때(즉 base case일때) calteam 함수에서 O(N)에 링크팀을 뽑아내는 것이 더 빠를 거에요. 스타트팀이 아닌 사람은 모두 링크팀일테니 걸러내기도 더 수월하실 겁니다.

kokodak   1년 전

음, 뭔가 O(N^2)으로 나타내니 좀 표현이 이상한 것 같아서 수정하자면, 2중 for문을 한 개의 for문으로 줄여서 한 팀의 인원만 확정시킨 뒤에, base case에 들어갈 때만 나머지 팀의 인원을 확정시키면 된다는 뜻이었습니다.

wldnjs3633   1년 전

감사합니다 해결됬어요^^

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