[BOJ알고리즘, C++]#1676_팩토리얼의 0의 개수, 소인수분해

 

[BOJ알고리즘, C++]#1676_팩토리얼의 0의 개수, 소인수분해

 

BOJ 알고리즘 문제 풀이, 1676_팩토리얼의 0의 개수

소인수분해의 성질을 이용해 N! 의 뒷자리 0의 개수를 구합니다.

 

---

 

문제

 

풀이

 

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

 

1. 먼저, 뒷자리 0을 만들기 위해 필요한 소인수는 2와 5입니다. (10 = 2 x 5, 10의 소인수분해) 
2. 1 ~ N 까지의 범위 내 숫자 중 소인수분해했을 때 나오는 '2' 혹은 '5'의 개수를 세는 겁니다.
3. 바꿔 말하면, 1 ~ N 범위 내 숫자 중 '2' 혹은 '5'의 배수들을 찾으면 됩니다!
4. '2' 보다 비교적 큰 '5'의 배수를 찾는 것이 더 효율적이겠죠.
5. 주의할 점은 '5'의 배수들 중 소인수분해했을 때, '5'가 두 번 이상 나오는 숫자들도 고려해야 합니다! (eg, 25, 50,...)
6. 그렇다면, 주어진 입력 값 N을 5의 제곱승으로 나눈 값들의 총합이 정답이 되겠습니다.
7. 위 그림을 보시면, 파란색 숫자는 소인수분해 시 '5'가 한 번 나오고, 빨간색 숫자는 두 번 나옵니다.
8. '5'를 한 번 세는 것을 N! 뒷자리 '0'의 개수 한 개로 치환하면, 쉽게 이해되실 겁니다.

 

코드 

/*  *************************************************************************************************************************************

    목적:
        소인순해의 성질을 이용해 1 ~ N까지의 숫자 중 소인수로 2 혹은 5가 나오는 횟수 카운트합니다.
    설명:
        1.  소인수 분해의 성질에 따르면, 뒷 자리에 0을 만들기 위해선 10을 소인수 분해하면 나오는 2와 5가 필요합니다.
        2.  1 ~ N 범위의 숫자들을 소인수분해 했을 때 비교적 2보다 5가 나오는 횟수가 적겠죠? 그래서 소인수분해로 5가 나오는 횟수를 세는겁니다.
        3.  세는 방법은 N/5^1 + N/5^2 + ... N/5^N

*   ************************************************************************************************************************************/

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int N;
    cin >> N;
    
    int ans = 0;
    for(int i=5; i<= N; i*=5)
    {
        ans += N/i;
    }
    cout << ans << endl;
}