[수학, DP] 백준 1676번 팩토리얼 0의 개수 c++, java 풀이

 

BOJ 1676번 팩토리얼 0의 개수 c++ 및 java 풀이

• 난이도: 실버3
• 백준 1676번 팩토리얼 0의 개수
  
  
  

문제 정리

1. N이 주어질때 N!의 맨 뒤에서 부터의 0이 아닌 숫자가 나올때 까지의 0의 개수를 구하여라
2. N은 0이상 500이하의 수이다.
   
   
   

문제 접근

처음에는 나이브하게 팩토리얄을 직접구해보려 했습니다.
하지만 역시나 20!까지 밖에 구할 수 없었습니다.
그래서 규칙을 찾아보았다. 16팩토리얄 까지 구해보면서 0의 개수가 군수열을 이루는것 같았습니다.
그래서 그렇게 풀었지만 실패...
그래서 다른 방법을 생각해보았습니다. 10이 몇개 곱해지는지 찾는 것!!
10이 몇개있는지 찾기 위해 인수분해하여 2와 5가 몇개있는지 찾아갑니다.
그리고 2와 5의 개수중 최소값이 10의 개수가 됩니다.
예를들어 120=2^3 x 3 x 5 입니다. 2는 3개 5는 1개 이므로 10은 1개 밖에 되지 않습니다. 이는 2와 5 인수 개수 중 더 작은 값입니다.

문제 풀이

1. 인수분해 했을때 2의 개수와 5의 개수를 담을 클래스를 생성하여 배열을 만듭니다.
2. 2!부터 계산해 나갑니다. i를 2로 나누어봅니다. 그렇게 하여 인수 2가 몇개있는지 탐색합니다. 5도 마찬가지 입니다.
3. 탐색한 다음 이전의 2와 5의 개수에 더합니다.
4. 그리고 둘 중에서 더 작은 개수를 찾으면 그것이 10의 개수가 되고 문제에서 원하는 0의 개수가 됩니다.
   
   
   

예시

예를들어 설명해보겠습니다. 간단히 5!의 0의 개수를 구해봅시다.

1. i=2 일때, 2의 개수는 1개입니다. 이전의 2와 5의 개수와 더하며 다음과 같습니다

   fact[2].two = fact[1].two + 1 = 1
   fact[2].five = fact[1].five + 0 = 0
   cnt[2] = min(0,1) = 0;

2. i=3 일때, 3!=6이므로 인수로 2를 하나가지고 있음을 압니다. 이는 2*3과도 같습니다.
   즉 이전의 2와 5의 개수에 새로 곱해지는 3의 2와 5의 개수만 알면 더해주면 됩니다.
   그러므로 fact[3].two = 1, fact[3].five = 0 입니다.
   cnt[4] = min(1,0) = 0

3. i=4 일때, 4!=24입니다. 이는 3!x4와 같습니다. 즉 3!일때 구한 2와 5의 개수에 새로 곱해지는 4의 2와 5의 개수를 구해서 더해주면 됩니다.
   4의 2의 개수는 2 이므로 fact[4].two = 3, fact[4].five = 0
   cnt[4] = min(3,0) = 0

4. i=5 일때, 5!=120입니다. 이는 4!x5와 같습니다. 이도 위에서와 마찬가지 방식으로 진행합니다.
   새로 곱해지는 수 5는 2는 0개, 5는 1개있습니다.
   fact[5].two = fact[4].two + 0 = 3
   fact[5].five = fact[5].five + 1 = 1
   cnt[5] = min(3,1) = 1
   즉 10이 한 개 있게 되어 0의 개수는 1개입니다.
   
   
   

백준 1676번 팩토리얼 0의 개수 c++ 코드

 

 

백준 1676번 팩토리얼 0의 개수 java 코드

 

 

 

풀이 인증