오늘을 배우고 내일을 개발하다

문제 링크 : https://www.acmicpc.net/problem/1676

[문제]

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

[알고리즘 분류]

• 수학

[해설]

문제에서 볼 수 있듯, 이번 문제는 N의 팩토리얼에서 0의 개수를 구하는 것이 목적이다.
N의 범위는 최소 0, 최대 500까지 주어지는데 이 때문에 직접 팩토리얼을 구해 0의 개수를 세려고 하면 숫자가 말도안되게 커져버려 일반적인 자료형으로는 담을 수도 없게 되어버린다.
따라서, 팩토리얼을 직접 구하는 것보다 일정한 규칙성을 찾는 것이 이번 문제의 포인트라고 할 수 있는데, 이 규칙성을 찾느라 좀 고생했던 것 같다.

이 규칙성을 찾기 위해서는 N에 대한 팩토리얼을 수행했을 때 0이 등장하는 수 N에 대한 규칙성을 알아야 한다.
예를 들어, 5!는 120인데 여기에서는 0이 한 번 등장한다. 그리고 문제에서 예시로 보여주는 10!은 3628800으로 0이 총 두 번 등장하게 된다. ( N이 가진 5의 배수의 수가 0의 개수라는 것을 알 수 있다. ex. 5는 5, 단 하나로 5의 배수가 1개, 10은 5와 10으로 5의 배수가 2개 )

여기에서 중요한 것은 5의 2,3,4...n승의 수들은 각각 5보다 5의 개수를 n-1개 만큼 더 가지고 있는 것과 마찬가지이기 때문에 N에 들어가는 5의 n승의 개수들도 같이 세어줘야 한다는 것이다.

결과적으로, 문제에서는 N의 범위를 최대 500까지로 제한하고 있기 때문에 500보다 작은 5^1 = 5, 5^2 = 25, 5^3 = 125에 대한 개수를 세어 모두를 더해주면 되는 것이다.

[정답 코드]

#include <stdio.h>

int main(){
  int N;
  scanf("%d",&N);
  printf("%d",N/5+N/25+N/125);
}

[결과]