알고리즘 문제 질문

Question

public static int get_zeros(int number) { int cnt &#61; 0; while(number >&#61; 5) { cnt &#61; cnt &#43; number / 5; number &#61; number / 5; } return cnt; }숫자를 하나 입력 받아서 해당 숫자의 팩토리얼 내에 포함되어 있는 5의 갯수를 리턴하는 메소드입니다예를 들어 25를 입력하면 25! &#61; 25 x 24 x 23 x 22 x 21 x 20 x 19 x 18 x 17 x 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1위의 곱셈에서 5가 몇 개인지를 리턴합니다. 그래서 처음에 25를 5로 나누어 5의 배수인 25, 20, 15, 10, 5를 셉니다 (몫 &#61; 5)여기까지는 이해가 가는데요 왜 몫이 5을 넘어가면 한번 더 5로 나누는 것이 제곱을 체크하는 것과 같은 지 머리로 도저히 이해도 납득도 안 가네요 ㅜㅜ코드 논리가 아니라 수학적으로 이해가 안 가는데 도움 부탁드립니다

엡실론 · Answer

25의 배수의 갯수는 n / 25 &#61; (n / 5) / 5

songline · Answer

해당 문제의 기본 풀이를 무식하게 표현하면 다음과 같습니다.1. N!을 이루는 각 숫자 중 5로 나눠서 나누어 떨어지지 않는 것은 버리고, 나누어 떨어지는 것만 모은다. 2. 남은 것들의 숫자를 센다. 3. 한 번 센 것을 또 세면 안되니까 각 숫자에서 5를 한칸씩 깎아낸다. 4. 하나도 남는 것이 없을 때 까지 &#34;1 ~ 3번&#34;을 반복한다. 5. 다 깎여서 사라지면 반복하면서 셋던 숫자들을 다 더한다.직관적으로 이해되죠? 여기서 우리는 입력된 숫자를 5로 나누면 5로 나누어 떨어지는 숫자, 즉 5의 배수가 몇개인지를 셀 수 있음을 알 수 있습니다. 그래서 2번을 다음과 같이 변경할 수 있습니다.1. N!을 이루는 각 숫자 중 5로 나눠서 나누어 떨어지지 않는 것은 버리고, 나누어 떨어지는 것만 모은다. 2. N / 5을 기록한다. 3. 한 번 센 것을 또 세면 안되니까 각 숫자에서 5를 한칸씩 깎아낸다. 4. 하나도 남는 것이 없을 때 까지 &#34;1 ~ 3번&#34;을 반복한다. 5. 다 깎여서 사라지면 반복하면서 셋던 숫자들을 다 더한다.위에서 5를 깎아낸다고 했는데 그것은 n * 5 에서 * 5를 떼어내는 행위로, 달리 말하면 / 5 를 하는 것과 같습니다. 그럼 다음과 같이 고칠 수 있습니다.1. N!을 이루는 각 숫자 중 5로 나눠서 나누어 떨어지지 않는 것은 버리고, 나누어 떨어지는 것만 모은다. 2. N / 5을 기록한다. 3. 모은 숫자들을 5로 나눈다. 4. 하나도 남는 것이 없을 때 까지 &#34;1 ~ 3번&#34;을 반복한다. 5. 다 깎여서 사라지면 반복하면서 셋던 숫자들을 다 더한다.헌데 N! 의 구성 숫자 중 나누어 떨어지는 것들만 모아놓으면 (N/5)! 와 모양이 같아집니다. 가령 33! 은 5의 배수만 모으면 30, 25, 20, 15, 10, 5 인데 각각 5로 나누면 6, 5, 4, 3, 2, 1 즉 6! 이 되죠. 이를 이용하면 1번과 3번을 축약할 수 있습니다.1. N / 5을 기록한다. 2. N &#61; N/5 를 한다. 3. 하나도 남는 것이 없을 때 까지 &#34;1 ~ 2번&#34;을 반복한다. 4. 다 깎여서 사라지면 반복하면서 셋던 숫자들을 다 더한다.하나도 남는 것이 없다 &#61; N이 0이다죠?1. N / 5을 기록한다. 2. N &#61; N/5 를 한다. 3. (N &#61;&#61; 0) 이 될 때까지 &#34;1 ~ 2번&#34;을 반복한다. 4. 다 깎여서 사라지면 반복하면서 셋던 숫자들을 다 더한다.뭐하러 나중에 더합니까. 바로 더해버립시다.1. 결과값에 N / 5을 더한다. 2. N &#61; N/5 를 한다. 3. (N &#61;&#61; 0) 이 될 때까지 &#34;1 ~ 2번&#34;을 반복한다.위 내용을 식으로 다듬으면 다음식이 됩니다.int get_zeros(number) { int output &#61; 0; while(number !&#61; 0) { output &#43;&#61; number / 5; number /&#61; 5; } return output; }이런 식으로 유도된 겁니다. 혹시 이해가 안되시면 말씀해주세요. 다른 방식으로 설명드리겠습니다.

알고리즘 문제 질문

2개의 답변

Q&A 목록