백준 1676 팩토리얼 0의 개수(JAVA)

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

 

 

풀이)

import java.util.Scanner;

public class Main_BJ_1676_팩토리얼0의개수 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;

        while(n >= 5){
            ans += n/5;
            n /= 5;
        }
        System.out.println(ans);
    }
}

당연히 안 되겠지만 처음엔 팩토리얼 수를 계산하고 10으로 나눠보는 방식을 사용했다.

이 방법은 당연히 시간 초과가 나왔다.

 

그 후, 끝자리가 0이 되려면, 소인수분해 했을 때 2와 5가 곱해지면 생긴다는 것을 생각해봤고,

5가 2보다 상대적으로 적게 나오므로, 5의 개수에 따라서 0의 개수가 달라짐을 깨달았다.

 

따라서 5의 개수를 세기 위해 n에서 5를 나눠주며 5의 개수를 세면 끝!

아이디어를 잘 생각해보쟝