scared22   1년 전

분자 분모가 2와 5를 찾아서 카운트를 증가시키는데 좀 더 빠르게 탐색하는 방법이 없을까요 ?

kyma123   1년 전

일일히 세는 것 보단 2와 5 각각의 거듭제곱으로 나눈 몫을 이용하는 게 훨씬 빠르겠죠.

그리고 1억이 넘는 케이스를 완전탐색 하면 대부분 TL 뜬다 생각하시는 게 좋습니다.

scared22   1년 전

이렇게 해도 TL이네요

kesakiyo   1년 전

http://www.geeksforgeeks.org/count-trailing-zeroes...

이 링크가 도움을 줄거라 생각합니다.

직접적인 솔루션은 들어있지 않지만 빠르게 2와 5의 개수를 셀 수 있게 해줄거에요.

kyma123   1년 전

음 그렇게 count에 ++하는 것 보단, n!의 뒷자리 0의 갯수 문제 풀듯이 푸는 쪽이 좋겠습니다.

우선 nCk = n! / k!(n-k)!이므로, n에 포함된 2와 5의 갯수를 다음과 같이 셉니다.

N2 = Σ[n/2k], k=1, 2, ..., N5 = Σ[n/5k], k=1, 2, ...

같은 방식으로 k와 n-k도 세 준 다음 그것을 뺀 후, N2와 N5 중 작은 값을 출력하면 되겠죠.

이 때 2k 혹은 5k가 32비트 정수라면 오버플로우가 일어날 가능성이 있으므로 처리를 따로 하시던지 64비트 정수로 선언하시던지 해야겠죠

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