5051번 - 피타고라스의 정리
고속 푸리에 변환을 통해 300ms에 풀이했습니다.
그런데 2명이 0ms의 시간으로 문제를 풀었다는 것을 알게 되었고, 방법이 궁금합니다...
그저 배열에 저장해두었다고 하기에는 500000개의 수를 모두 저장하면 코드가 1000바이트 단위일 수가 없는 것 같은데, 수학적인 풀이가 존재하나요?
기본적으로는 0을 사용하는 경우를 포함하는 답을 먼저 구한 뒤 포함배제의 원리를 사용해 0이 들어가는 쌍들을 제외하는 방향이고, 이때 필요한 값들을 수학적인 방법으로 (O(1)까지는 아니지만) 빠르게 얻을 수 있었던 것으로 기억합니다.
쉽지 않네요… 감사합니다
댓글을 작성하려면 로그인해야 합니다.
luckyandykang 1년 전
고속 푸리에 변환을 통해 300ms에 풀이했습니다.
그런데 2명이 0ms의 시간으로 문제를 풀었다는 것을 알게 되었고, 방법이 궁금합니다...
그저 배열에 저장해두었다고 하기에는 500000개의 수를 모두 저장하면 코드가 1000바이트 단위일 수가 없는 것 같은데, 수학적인 풀이가 존재하나요?