[JAVA] 백준 1676번 : 팩토리얼 0의 개수

 

---

 

• 생각

1. 이런 문제들은 대부분 규칙이 있다. 

 

위의 사진으로 보면 이해가 잘 될 것이다. 5의 배수마다 0의 count 값이 증가하는 것을 볼 수 있다. 

 

근데 중요한 점은 입력값이 25일 때 1씩 증가하던 count 값이 2가 증가한다.

 

이유는 뒷자리가 0이 n개 있다는 의미는 2와 5개 n개씩 짝지어 존재한다는 것이다.

팩토리얼 값을 보면 2는 5보다 작은 수여서 연속된 수를 곱하게 되면 자연스럽게 모든 값들의 소인수 분해들은 2의 개수가 5의 개수보다 많다.

 

즉, 기본적으로 5의 개수에 따라 값이 변화한다고 볼 수 있다. 

 

• 코드

정답 코드 : 단순히 5로 나눌 것이 아니라 반복문을 통해 5로 나누면서 누적합을 구해주면 된다.

 

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

public class Algorithm {
	static int N;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(CountZero());
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        N = Integer.parseInt(br.readLine());
	}

	private static int CountZero() {
		int count = 0;
		while (N >= 5) {
			count += N / 5;
			N /= 5;
		}

		return count;
	}
}