반응형

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

예제 입력 1

10

예제 출력 1

2

나의 풀이

이 문제를 풀기 위해서 1부터 순서대로 팩토리얼을 구해보다가 5, 10, 15를 기점으로 0이 하나씩 증가하는 것을 보고 5와 관련이 있구나!라는 생각으로 문제를 풀다가 우연히 단계별 풀이에 소인수분해를 활용이라는 힌트를 보게되어 각각의 수들을 소인수분해를 해보니 0의 개수는 곧 5의 개수 였다. 왜냐하면 2*5가 생길때마다 10으로 0이 뒤에 하나씩 붙게되고 이후에 어떠한 수를 곱하게되더라도 이 0의 개수는 증가하면 증가하지 없어지지는 않았다.

그래서 이 문제는 i를 1부터 n까지 증가를 시키면서 5로 나누어 떨어지는 수들에 대하여 5로는 더 이상 나누어떨어지지 않을때까지 반복을 하며 count수를 증가시키면 되었다.

이렇게 풀고나서 정답은 다 제대로 나오는거 같은데 문제가 90몇퍼에서 틀려버렸다... 알고보니 n이 0으로 주어질때 였다. 나는 처음에 0일때도 0이 하나있으니까 0일때는 1을 출력해주었는데 그러면 안되었었다... n이 0일때에도 0이어야한다.


코드

import java.util.Scanner;

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

        int count = 0;

        for (int i = 1; i <= n; i++) {
            if (i % 5 == 0) {
                int j = i;
                  // 5로 나누어 떨어지지 않을때까지 반복
                while (j % 5 == 0) {
                    count++;
                    j = j / 5;
                }
            }
        }

        System.out.println(count);
    }
}
반응형

'Programming > Algorithm' 카테고리의 다른 글

[백준10773번] 제로  (0) 2020.01.24
[백준10828번] 스택  (0) 2020.01.24
[백준9375번] 패션왕 신해빈  (0) 2020.01.19
[백준11051번] 이항 계수 2  (0) 2020.01.19
[백준11050번] 이항 계수 1  (0) 2020.01.19

BELATED ARTICLES

more