알고리즘/리트코드 (1) 썸네일형 리스트형 172번 Factorial Trailing Zeroes 풀이(c++) 풀이 해설을 요청하신 분이 있어서.. 이 문제는 'trailing zero'을 구하는 문제이다. 숫자의 가장 뒤에 연속해서 붙어오는 0의 갯수를 세는 문제라고 말해도 될것같다. (단 0인경우에는 숫자를 세지 않는다) 처음에는 주어진 숫자를 문자열로 바꿔서 맨 뒤에 있는 0의 갯수를 세는걸로 생각했지만, 더 효율적인 방법이 있을거라 판단하고 생각하다보니 한 가지 규칙을 발견하게 되었다. n! = x * 10^r 맨 뒤에 연속해서 오는 숫자가 r이라고 할 때, 위와 같은 수식으로 문제를 바꿔서 표현할 수 있다. 오히려 '맨 뒤에 있는 0의 갯수'보다 위 식이 훨씬 간결하고 정확하게 문제를 정의하고 있다. 즉, n!을 소인수분해하여 나오는 10의 갯수가 이 문제의 정답이 된다. 10을 소인수분해하면 '2*5'.. 이전 1 다음
