luckyandykang   1년 전

고속 푸리에 변환을 통해 300ms에 풀이했습니다.

그런데 2명이 0ms의 시간으로 문제를 풀었다는 것을 알게 되었고, 방법이 궁금합니다...

그저 배열에 저장해두었다고 하기에는 500000개의 수를 모두 저장하면 코드가 1000바이트 단위일 수가 없는 것 같은데, 수학적인 풀이가 존재하나요?

doju   1년 전

기본적으로는 0을 사용하는 경우를 포함하는 답을 먼저 구한 뒤 포함배제의 원리를 사용해 0이 들어가는 쌍들을 제외하는 방향이고, 이때 필요한 값들을 수학적인 방법으로 (O(1)까지는 아니지만) 빠르게 얻을 수 있었던 것으로 기억합니다.

luckyandykang   1년 전

쉽지 않네요… 감사합니다

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