[백준 - 1676][Python] 팩토리얼 0의 개수

안녕하세요. 성조입니다.

이 포스팅은 Python 3 버전을 기준으로 풀이됐습니다.

 

 

성능

문제 중간에 잘못 접근한 부분들이 존재해서 바로 바꾸고 다시 접근했습니다.

 

 

문제 출처

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

1676번: 팩토리얼 0의 개수

---

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

 

출력

첫째 줄에 구한 0의 개수를 출력한다.

 

코드

import sys

N = int(sys.stdin.readline())
cnt = 0

while N > 0:
    cnt += N // 5
    N //= 5
    
print(cnt)

 

풀이

이 문제를 초반에 접근하는데 입력받은 값을 팩토리얼 구현 후 0이 아닌 숫자가 나올 때 까지 계산하는 것으로 이해를 했다.

(N을 나누는 값도 N /= 5 연산 후 출력에서 int로 묶기도 했다.)

 

재귀 함수로 1부터 10까지 다 대입해서 본인이 생각한 N! 연산이 끝나고, 0이 몇개 존재하는지 체크하는 문제가 맞는지 체크했다.

 

1인 경우. = 1

2인 경우. = 2

3인 경우. = 6

4인 경우. = 24

5인 경우. = 120 (0이 존재하기 시작한 숫자)

6인 경우. = 720

7인 경우. = 5040

8인 경우. = 40320

9인 경우. = 362880

10인 경우. = 3628800 (예제에서 0이 존재하는 값이 2개가 있다 얘기한 케이스다.)

 

 

3는 [2 * 3] -> 0개

4는 [2^3 * 3] -> ?개

5인 경우 120를 소인수 분해하면 [2^3 * 3 * 5]가 나온다. -> ?개

6은 [2^4 * 3^2 * 5] -> ?개

7은 [5^7 * 3^2 * 5 * 7] -> ?개

8은 [2^7 * 3^2 * 5 * 7] -> ?개 

9는 [2^7 * 3^4 * 5 * 7] -> ?개

10은 [2^8 * 3^3 * 5^2 * 7] -> 2개를 갖게 된다.

 

출력 예제를 보면 3은 0개를 가지며, 10은 2개 갖는다.

3을 예로들면 2*3 = 6인 경우.

6은 0을 가지고 있지 않다.

 

10을 예로들면 [2^8 * 3^3 * 5^2 * 7] 중 두 값을 곱했을 때 2*5 = 10만 뒷 자리가 0을 만족한다. 그렇게 5의 개수를 찾아내는 것을 목표로 한다.

 

이 문제에서 소인수분해했을 때 5의 값이 존재하는 경우만 카운팅하면 위에 ?개로 표시한 값들은 다음과 같아진다.

4 -> 0개

5 -> 1개

6 -> 1개

7 -> 1개

8 -> 1개

9 -> 1개

10 -> 2개

 

5를 나누는 연산을 한다.

while 입력 변수가 0보다 큰 경우만:
    카운팅 된 값 += 입력된 값 // 5
    입력된 값 //= 5

 

 

 

---

오타나 이해가 안가는 부분이 있다면 언제든지 댓글로 얘기해 주시면 감사드리겠습니다.

 

다음 포스팅 때 뵙겠습니다.