5의 갯수만 구했습니다. 그런데 예외가 있을까 싶어 질문합니다.

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

28. N!에서 0의 개수(소인수분해 응용)

작성

278

저는 n!에서 10이 나오려면 무조건 5가 몇갠지만 체크하면 된다고 생각했습니다.

왜냐하면 우선 5!일 때 5의 갯수가 1개 있기 때문에 10이 나오기 때문입니다. 이미 5!일 때부터 5의 갯수는 1개, 2의 갯수는 3개니까요.

5의 제곱인 25!이라고 해도 5의 갯수는 겨우 5개인 반면 2의 갯수는 2~8까지만 봐도 이미 5개를 넘겼으니까요.

그래서 저는 그냥 5의 갯수만 세서 5의 갯수가 뒤에 붙는 0의 숫자라고 풀었습니다만 정말 만에 하나 예외가 있을 수도 있으니까요... 예외가 있는지 궁금합니다!

답변 1

지식공유자

안녕하세요^^

네. 그렇게 해도 상관없습니다. 2는 모든 짝수가 인수로 가지고 있는 숫자이지만 5는 모든 홀수가 가지고 있는 인수가 아니기때문에 N!의 경우를 소인수분해하면 2가 5보다는 더 많이 나오는 것 같습니다. 그리고 경험치에 의한 논리로 봐도 반례는 없어 보입니다.

실제 코테시험에서도 이런 경우 생각한대로 시도해보고 통과가 안되면 "반례가 있나?" 이렇게 생각하고 보완하면 되겠죠. 이 경우도 5의 개수를 답으로 해보고 통과안되면 영상처럼 해보는 거죠. 너무 걱정하지 않아도 됩니다. 여튼 제 생각에는 반례가 없어 보입니다.

질문자

넵 감사합니다!!

인프런 커뮤니티 질문&답변