chogahui05   4년 전

테케가 허술한 거 같은 기분이 듭니다만.. 그것까지는 잘 모르겠습니다.

그렇지만, 느낌상 이건 안 될 거 같은데.. 덜컥 하고 된 거 보고 상당히 당황스러웠습니다.


일단 C가 최대 10만까지고, A, B, C 입력 셋트가 100개까지 들어오기 때문에

제 방식으로 풀면 빨라봤자 O(1000만(log1000만))이라 시간초과는 면하기 어려울 거 같습니다.

그리고 시간초과를 면한다고 해도, 솔직히 어마무시한 반례가 있을 거 같습니다.


제 풀이는 이렇습니다.


(1) 2147483647 (2^31-1은 메르센 소수더라고요.. 일단 이걸로 나눠봤습니다.) 로 나눠봐서 나머지가 같다면

(2) log10 함수를 이용해서 자릿수를 소숫점 8자리까지 구해봐서


(1)과 (2)가 같다면 같은 수라고 판단했습니다.

그런데 조건 (1)만을 적용해 보니 10%에서 틀렸습니다. 가 뜨는 걸로 봐서는

충돌할 확률이 거의 없다는 것이지 아예 없는 건 또 아니더라고요.


그렇다고 (2)까지 조건을 둬서 검사하자니

소숫점 오차 때문에 아주 미세하게 다른 수는 또 구분을 못 할 듯 싶고요..

예를 들어서 a가 60만 자리이고 b가 a+2147483647이라면

로그값의 차이는 거의 안 난다고 봐도 되니까요.


(1)만 가지고 판단했을 때 10%에서 틀렸습니다가 떳기 때문에

(1) + (2)를 넣는다면 매우 매우 큰 수에 대해서 제 방식이 잘못된 답을 낼 수 있을 거 같은데요..

반례가 없는지 궁금합니다..

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