kingsubin

package soup.algorithms.boj;

import java.util.Scanner;

public class boj_1676 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;

        for (int i = 5; i <= n; i*=5) {
            ans += n/i;
        }

        System.out.println(ans);
    }
}

 

- N 의 범위가 500까지인데 500! 구하는건 오래걸리고 수가 너무 크다 -> 다른 방법 생각

- 0이 뒤에 몇개가 오는가 ? -> 0이 될려면 소수 2 * 5가 되어야하고 결국 2 * 5가 몇 번 등장하는가 ?를 묻는것

- 어떤 수를 소인수분해 했을경우 2보다는 무조건 5가 적을수 밖에 없고 그렇다면 5의 등장 횟수를 찾아야한다.

- 1 ~ N의 수를 소인수 분해햇을경우 5의 등장횟수는 5를 나눈 몫과 같다.

- 그런데 25의 경우에는 5가 2번 등장, 125의 경우에는 5가 3번 등장 -> for문에서 증가값에 i *= 5를 줘서 추가로 카운팅해준다.