알고리즘 :: 백준 :: 3474 - 교수가 된 현우

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

• 입력: 테스트 케이스 T
• 입력: 각 테스트 케이스마다 정수 1 ≤ N ≤ 1,000,000,000
• 출력: $N!$를 나타냈을 때 오른쪽 끝에 있는 0의 개수

✏️ 문제풀이

당연히 `int`든 `unsigned long long`이든 수의 범위를 가볍게 넘어가기 때문에 직접 계산하는 문제가 아닙니다 ㅎㅎㅎ

 

0을 만들기 위해서 필요한 '재료'는 2와 5가 있습니다.

• $N!$를 나열하는 과정에서 2, 4, 6, 8 ... 정말 많은 2가 생성됩니다. 즉, 2라는 재료는 넘쳐난다는 뜻입니다.
• 따라서, 0을 만들기 위한 '핵심재료'는 5입니다. $N!$ 속에 5가 몇 개 있느냐에 따라 0의 개수가 결정됩니다.

코드로 나타내면 정말 간단합니다.

for (int i = 5; i < N; i *= 5) answer += (N / 5);

• N 속에서 5의 배수 개수를 뽑아내고,
• N 속에서 25의 배수 개수를 뽑아내고, (5가 2개인 아이들이라 1번씩 더 더해줘야)
• N 속에서 125의 배수 개수를 뽑아내고... (5가 3개인 아이들이라 1번씩 더 더해줘야)

혹시라도 잘 이해가 안 되신다면, $26!$를 한 번 생각해보세요.

26  25 ... 20 ... 15 ... 10 ... 5 ...
    2      1       1      1     1
    26 / 5 = 5, 26 / 25 = 1
= 0이 6개

$26!$ 속에는 위와 같이 총 6개의 5가 숨어있습니다. 따라서 오른쪽 끝 0이 6개 붙을 거라는걸 알 수 있습니다.

이걸 식으로는 $26 / 5 + 26 / 5^2$으로 표현할 수 있겠습니다.

📝 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T;
	cin >> T;
	while (T--) {
		int N;
		cin >> N;
		
		int answer = 0;
		for (int i = 5; i <= N; i *= 5) answer += (N / i);
		cout << answer << '\n';
	}
}

 

🔗 코드 링크

🕧 결과