fman1335   2달 전

여서 어떻게 더 빠르게 할 수 있나요??

jjwdi0   2달 전

38~46 줄까지 2중 for문이 돌아가서 이 코드의 시간복잡도는 O(N^2)입니다.


자세히 관찰하시면 (?) 불필요한 계산이 돌아감을 알 수 있으실 겁니다.

38~46 줄을 O(N)에 처리하는 방법을 찾으시면 될 것 같습니다. (공들이 이미 크기 순으로 정렬되어 있음을 이용하시면 됩니다.)

fman1335   1달 전

모르겠습니다...ㅠㅠㅠ

jjwdi0   1달 전

음... 그러니까 공들을 크기 순으로 소트할때 있잖아요

40번째 줄부터 점수를 더할 때 첫 번째 공부터 점수를 더하는데

공들이 크기 순이므로 점수를 계속해서 더할 필요 없이 계속 그 값을 누적시켜가면 더 효율적으로 구할 수 있습니다.

제가 설명을 잘 못해서ㅠㅠ 죄송합니다ㅠ

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