[알고리즘] 3474번: 교수가 된 현우

0. 문제

 

3474번: 교수가 된 현우

 

---

1. 문제이해

 

1. c++의 int는 –2,147,483,648 ~ 2,147,483,647 범위를 가진다. 대략 -20억 ~ 20억.
2. 주어지는 N의 범위는 (1 <= N <= 1,000,000,000) int로 N!는 커버가 되지 않는다.
   1. 실제로 곱셈을 수행하지 않고 0의 개수를 구하는 방법.

 

• 1! = 1 → 0개
• 2! = 1! * 2 = 2 → 0개
• 3! = 2! * 3 = 6 → 0개
• 4! = 3! * 4 = 24 → 0개
• 5! = 4! * 5 = 120 → 1개
• 6! = 5! * 6 = 720 → 1개
• 7! = 6! * 7 = 5040 → 1개
• 8! = 7! * 8 = 40320 → 1개
• 9! = 8! * 9 = 362880 → 1개
• 10! = 9! * 10 = 3628800 → 2개
• 11! = 10! * 11 = 39916800 → 2개
• 12! = 11! * 12 = 479001600 → 2개
• 13! = 12! * 11 = 6227020800 → 2개
• 14! = 13! * 12 = 87178291200 → 2개
• 15! = 14! * 15 = 1307674368000 → 3개

 

5의 배수마다 오른쪽 마지막 0의 개수가 하나씩 증가함.

 

N을 5로 나눈 값을 구하면 된다.

 

// 예시 입력
6
3
60
100
1024
23456
8735373
// 예시 출력
0
14
24
253
5861
2183837

60을 5로 나누면 12인데 출력값은 14다.

 

이유는 25, 50의 경우 5가 2번 곱해지기 때문이다.

 

75도 100도 2번 곱해진다.

 

또한 125는 3번 곱해진다.

 

N을 5로 나눈 값 + 5*5로 나눈 값 + 5*5*5로 나눈 값 + …을 구해야 한다.

 

ex) 1024 = 204 + 40 + 8 + 1 = 253

 

1. T번 동안…
2. ret = 0;, i=5;
3. N >= i이 ...
   1. 참이면 ret += N/i; i*=5;하고 3번 반복
   2. 거짓이면 cout ret;하고 다음 입력 처리.

 

---

2. 제출

//백준 3474번: 교수가 된 현우
#include<iostream>

using namespace std;

int T;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  cin >> T;
  for(int tc = 1; tc <= T; tc++){
    int N, ret=0, i=5;
    cin >> N;
    while(N >= i){
      ret += N/i;
      i*=5;
    }
    cout << ret << "\n";
  }

  return 0;
}

규칙을 모르겠으면 직접 다 해보면 된다.

 

---