
안녕하세요. 성조입니다.
이 포스팅은 Python 3 버전을 기준으로 풀이됐습니다.

문제 중간에 잘못 접근한 부분들이 존재해서 바로 바꾸고 다시 접근했습니다.
문제 출처
https://www.acmicpc.net/problem/1676
1676번: 팩토리얼 0의 개수
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
문제
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
오타나 이해가 안가는 부분이 있다면 언제든지 댓글로 얘기해 주시면 감사드리겠습니다.
다음 포스팅 때 뵙겠습니다.
'백준 - Python' 카테고리의 다른 글
[백준 - 1874][Python]스택 수열 (0) | 2023.02.19 |
---|---|
[백준 - 1302 ][Python] 베스트셀러 (0) | 2023.02.15 |
[백준 - 11931, 15688][Python] 수 정렬하기 4, 5 (0) | 2023.02.10 |
[백준 - 1002 ][Python] 터렛 (0) | 2023.02.09 |
[백준 - 1026][Python] 보물 (0) | 2023.02.08 |

안녕하세요. 성조입니다.
이 포스팅은 Python 3 버전을 기준으로 풀이됐습니다.

문제 중간에 잘못 접근한 부분들이 존재해서 바로 바꾸고 다시 접근했습니다.
문제 출처
https://www.acmicpc.net/problem/1676
1676번: 팩토리얼 0의 개수
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
문제
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
오타나 이해가 안가는 부분이 있다면 언제든지 댓글로 얘기해 주시면 감사드리겠습니다.
다음 포스팅 때 뵙겠습니다.
'백준 - Python' 카테고리의 다른 글
[백준 - 1874][Python]스택 수열 (0) | 2023.02.19 |
---|---|
[백준 - 1302 ][Python] 베스트셀러 (0) | 2023.02.15 |
[백준 - 11931, 15688][Python] 수 정렬하기 4, 5 (0) | 2023.02.10 |
[백준 - 1002 ][Python] 터렛 (0) | 2023.02.09 |
[백준 - 1026][Python] 보물 (0) | 2023.02.08 |