[백준/Java] 1676번 팩토리얼 0의 개수

 

문제 풀이

이 문제는 정수의 특징을 알고 있으면 쉽게 풀 수 있는 문제이다.

 

문제에서 요구하는 결과는 숫자 10000가 있다면 일의 자리부터 0이 아닌 숫자가 나올 때까지 올라가며 다른 숫자를 만날때까지 0의 개수를 구하는 것이다.

10000이 주어진다면 0의 개수는 4가 될 것이고, 10100이 주어진다면 0의 개수는 2가 될 것이다.

 

그렇다면 숫자들의 곱에서 0이 나올 수 있는 숫자들은 뭐가 있을까 ?? 바로

 

2 와 5 의 곱이다.

 

위의 예시를 보자.

일단 15는 일의 자리에 0이 존재하지 않는다.

15를 소인수 분해하면 3 x 5로 나타낼 수 있다. 2는 존재하지 않는다는 것을 보여주기 위해 2의 0제곱을 넣어줬다.

15에 대한 2의 지수는 0개 5의 지수는 1개가 된다. (파란색 글씨 참고)

5의 지수는 1개가 있지만 2의 지수는 없기 때문에 15에서는 일의 자리에 0이 존재하지 않는 것이다.

 

다음으로 10을 보자.

10을 소인수 분해하면 2 x 5로 나타낸다.

2의 지수는 1, 5의 지수는 1이다.

둘 다 1이기 때문에 10에서 일의 자리가 0이 된다.

 

마지막으로 100을 보자.

100을 소인수 분해하면 2의 제곱 x 5의 제곱으로 나타낸다.

2의 지수는 2, 5의 지수는 2이다.

각각 지수를 2개씩 가지고 있기 때문에 일의 자리, 십의 자리가 모두 0이 된다.

 

그런데 위의 예시와 같이 2의 지수와 5의 지수가 달라질 때가 있다.

이때는 2의 지수와 5의 지수 중 최소값을 구해야 0의 개수를 알 수 있다.

2의 지수 = 1  | 5의 지수 = 2 의 최소값은 1이다.

그래서 50에서 일의 자리만 0이 된다.

 

그럼 코드를 보자.

 

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
int N = Integer.parseInt(bf.readLine());

1. 문제에서 주어진 N을 입력 받는다.

 

int five = solve(N, 5);
int two = solve(N, 2);

2. solve라는 함수를 만들어 N에 대한 5의 지수와 2의 지수를 구한다.

인자로는 N과 지수가 무엇인지 알고 싶은 숫자를 넘긴다.

 

public static int solve(int n, int div) {
    int cnt = 0;
    for(int i=div; n/i>0; i*=div) {
        cnt += n/i;
    }

    return cnt;
}

3. 지수의 개수를 담을 cnt 변수를 생성한다.

최소한을 반복하기 위해

초기화 : 구하고 싶은 지수

조건식 : i가 n 이하인 동안

증감식 : 지수의 배수로 증가

 

만약 solve(100, 5)가 입력되었다고 가정하자.

그럼 아래와 같이 실행될 것이고,

100! 에 대한 5의 지수의 개수는 총 24개가 된다.

2의 지수도 마찬가지이다.

 

 

System.out.println(Math.min(five, two));

4. 5의 지수와 2의 지수 중 최소값을 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(bf.readLine());
		
		int five = solve(N, 5);
		int two = solve(N, 2);
		System.out.println(Math.min(five, two));
	}
	public static int solve(int n, int div) {
		int cnt = 0;
		for(int i=div; n/i>0; i*=div) {
			cnt += n/i;
		}
		
		return cnt;
	}
}

 

 

이 문제와 비슷한 응용 문제 하나 추천하고 간다 ! 😊

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

 

 

 

 

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