백준 C++ 1676번 팩토리얼 0의 개수 ( 감별, 소인수분해 )

 

 

4월 1일은 만우절!

만우절 만우절

 

고등학교 2학년 때

만우절 장난친다고

야자 하다가

한 명씩 쓰러지는 연기했던 생각이 나요.

그때 제가 두 번째로 쓰러졌었는데

 

선생님이 물 뿌려야겠다고 물을 가져오셔서 첫 번째 친구는 일어났지만

저는 꿋꿋하게 일어나지 않았습니다.

 

그때 선생님의 목소리가

저는 아직도 기억에 나요.

 

정말 오래됐는데 말이죠.

 

오래오래 기억될 추억이에요 저한테는

선생님께는 어땠을지...

궁금하긴 해요 ㅎ

 

---

 

흠..

일단 팩토리얼 함수를 구현할 줄 알아야 하는 거 같다.

 

저번에 만들었었는데..

기억 못 한다.

 

긁적

 

1. 팩토리얼함수를 만들어야 한다.

 

2. 뒤에서부터 라고 했으니까 % 나 / 를 써서

앞으로 당겨서..? 0이 아닌 숫자가 나왔을 때 뒤에 0의 개수 구하기.

 

 

팩토리얼 함수 힌트 보기 위해

인지 씨를 찾은 나

 

하지만 인지 씨는 나에게

매우 무서운 함정에 대해 이야기해 주었다.

 

 

13! 만 되어도 숫자가 이상해진다고 

int에서 벗어난다며..

13! 이면..

계산기로 두들기니

13! = 6,227,020,800

 

.. 어 32억이 넘네..

벌써 int가 넘어가며

20! 이 되면 long long으로도 쓸 수가 없다고 한다.

 

그래서 

이 친구가 말하는 것은

 

0을 어떻게 만들어지는지 생각해 보라고 했다.

 

0을..? 0을 곱하진 않는데.. 어떻게 0을 만드는 거지?

10을 만들라고 했다. 10을 곱하면 0이 생기지 않냐고

10..! 10은 또 2랑 5랑 곱하면 된다.

 

그래서 얘 말은

2와 5의 쌍이 몇 개인지 찾으면 된다!!

 

 

1부터 N까지 곱할 때

2는 많이 나오는 편이다

2,4,6,8,10....

근데 5는 가끔만 나온다.

5,10,15,20

 

그래서 우리는 5가 몇 번 들어가는지 찾으면 된다.

 

근데 이렇게 쉽다고?

 

그럴 리가 없지

틀렸단다.

 

i가 25면 어쩔 거냐 이거다

5가 두 개인데

너는 한 번만 더한다!..

 

그렇군....

 

 

숫자 복사 해놓고! 나눌 거니까

while문을 써서

되는데 만큼 돌려보기

 

이렇게 다했는데

 

더 재밌는 식이 있다고 알려주었다.

 

어차피 5의 배수만 구할 거고

글자수는 500이 제한이니까

그냥 cnt = ( n /5 ) + ( n / 25 ) + ( n / 125 ) ;

 

해주면 된다고 한다..

진작 알려주지..

 

 

 

긁적..

참 쉬운 문제가 되어버렸다.

 

---

 

나는 이런 생각을 못하는데..

참 대단한 문제다.

 

1. 일단 500을 보며 감당할 수 없는 숫자인걸 깨달아야 하고

2. 다른 방법이 있을 거라고 생각해야 한다.

3. 그 방법은 0의 개수를 찾는 거니까

10을 만드는 방법에 대해 생각해야 하고

10은 2 * 5 이까

세트를 찾는 건데

2는 너무 많으니까 5의 개수가 10을 만들 개수를 담당하게 된다.

5가

두 번 나올 25

세 번 나올 125

 

횟수를 세면 된다.

 

 

그리고 인지 씨는

컴퓨터를 계산기로 쓰지 말고 감별사로 써보라고 하셨다.

감별사라...

 

어렵다.

 

 할 수 있을지 모르겠다.