[BOJ] 3473 교수가 된 현우 - JAVA

1. 문제

3474번: 교수가 된 현우

알고리즘의 킹갓제너럴엠퍼러마제스티충무공알고리즘마스터 현우가 교수로 취임하였다!

그러나 학생들에게 크나큰 기대를 품고 첫 수업에 들어갔던 현우는 아무도 외판원 순회 문제(Traveling Salesman Problem, TSP)를 풀지 못하는 것을 보고 낙심하였다.

그 와중에 학생 남규는 TSP를 완전탐색으로 풀려고 하였고, 현우는 그걸 보고 경악을 금치 못한다. 왜냐면 TSP를 완전탐색으로 풀려면 O(N!)의 시간이 소모되는데, 이는 경악을 금치 못할 시간이기 때문이다.

그러나 남규는 O(N!)이 왜 큰지도 잘 모른다. 그래서 현우는 더더욱 경악을 금치 못하고, N!이 얼마나 큰지 대략적으로나마 알려주기 위해, 자연수 N이 주어지면 N!의 오른쪽 끝에 있는 0의 개수를 알려주기로 하였다.

그러나 현우는 경악을 금치 못하여 지금 코딩을 할 수 없는 상황이다. 여러분이 현우를 대신하여 프로그램을 작성하시오.

---

2. 풀이

오른쪽 끝에 0이 몇개 있는지는 2,5의 개수를 각각 세서 더 작은쪽의 개수로 알 수 있다. 하지만 항상 2보다 5가 적으므로 5가 몇개 있는지만 세면 0의 개수를 알 수 있다.

위의 표처럼 문제를 풀었다.

5부터 24까지는 1개씩,

25부터 124까지는 2개씩,

125부터 624까지는 3개씩 '5'가 있다.

따라서 num을 5,25,125,, 등등 5의 제곱수로 나눠서 나오는 몫을 차례차례 더하면 된다.

 

예를 들어서 num이 26이라면, 5의 개수가 한 개 이상인 수가 총 26/5=5개 있을 것이다.

5의 개수가 두 개 이상인 수는 26/25=1개 있을 것이다.

따라서 num이 26일 때 5+1=6개의 '5'가 존재한다. 중첩해서 더한다고 생각하면 된다!

import java.io.*;
import java.util.*;

public class BOJ_3473_교수가된현우 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());

      StringBuilder sb = new StringBuilder();
      int num, count;
      for(int i=0;i<N;i++){
         num = Integer.parseInt(in.readLine());
         count = 0;
         for(int n=5;n<=num;n*=5) {
            count+=num/n;
         }
         sb.append(count).append('\n');
      }

      System.out.print(sb);
   }
}

---

3. 결과

문제조건까지 배열칸수를 늘렸더니 메모리초과났다.