[Algorithm] Swift 백준 1676번

 

 

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

1676번: 팩토리얼 0의 개수

 

문제접근 

 

문제 이해를 하는데 오래 결렸음. 문제가 짧은걸 보고 쉬워 보여서 무작성 구현하려고 들어가서 다시 발을 뻈다. 😂

결국 정해진 시간까지 문제를 풀지 못함

 

정답풀이 

정답을 찾아보아도 이해가 힘들었다. 시간이 결렸고..

차근차근 어떻게 이해를 해보았는지 설명해 보겠음

 

자! ~ 그러면 문제먼저 보자!! 

 

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

 

라고 문제가 주어짐

 

N! 는 팩토리얼을 의미하는데 

 

팩토리얼(factorial)은 n이 자연수일 때, 1부터 n까지의 모든 자연수의 곱을 의미함.

 

 N 팩토리얼은 N!으로 표시함. 

 

 

위와 같이 계산하게 되는 거임! 

 

이제 팩토리얼은 다시 한번 알아봤고!  다시 문제를 보면 

 

뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하라고 함.

 

 

N의 값이 5를 기준으로 본다면 0의 개수가 1개가 됨 

 

Swift에서 팩토리얼을 직접 계산한다고 했을 때는 5처럼 작은 값을 괜찮지만 

 

첫째 줄에 N이 (0 ≤ N ≤ 500) 500까지 가능하다 보니 

 

최대 500!이라는 큰 수를 기본 자료형인 Int로 나타내기는 어려울 것임 

 

대략 

 

 

이 정도인 듯 

 

그렇기에 다른 방법으로 0의 개수를 구해주어야 함.

 

 

다시 가져와보면 가장 먼저 0이 나오는 N! 은 5 임

 

어떻게 0이 나오는지 보면 

 

 

5! 를 보면 5부터 1까지 곱하는 과정에서 4x3x1 = 12가 나오고 아직까지 0이 나올 수가 없음.

 

근데 5x2 = 10을 곱하는 순간 120이 되면서 0이 생겨남! 

 

2는 짝수에 대해 모두 약수이므로, 2가 나오는 횟수는 따로 고려하지 않고 5의 횟수를 구하면 됨

 

쉽게 말하면~  2는 4에도 포함되어 있기 때문에 사실상 5만 고려해 줘도 된다는 말임!! 

 

그렇게 되면 N이 5 이상인 값들은 0이 1개 이상 있다는 말이 됨

 

그럼 100! 은 0이 몇 개가 있을까?? 🤔

 

앞에서 봤던 거처럼 5의 개수가 0의 개수를 만들어 내기 때문에 5의 개수를 알아보면 총 24개가 나온다! 

 

 

실제 계산도 24개가 나옴! 

 

근데 여기서 주의할 점을 보면 25, 50, 75, 100을 보면 5가 2번씩 나오게 되는데! 

 

5가 두 번 나온다는 뜻은 == 0이 두 번 나온다!!! 라는 말과 같음 

 

5가 두번 나오는 것 즉!!  5^2 = 25를 따로 고려해줘야 하는 말임!! 

 

그리고~ 

 

N는 500까지 가능하기 때문에 5^3까지는 나올 수 있음!! 5^4는 625 이므로 안됨!! 

 

그러면 5^3= 125도 고려해줘야 함!! 

 

결국 5, 5^2, 5^3 3 3가지를 고려해 주면 됨!! 

 

let n = Int(readLine()!)!
print(n / 5 + n / 25 + n / 125)

 

코드는 정말 간단함! 

 

 

 

문제 풀이를 이해하려고 글로 적으면서 하니깐 훨씬 내 머릿속에 잘 들어왔음!! 

이번처럼 그냥 코드만 짜려고 컴퓨터만 보지 않고, 직접 계산을 해보면서 문제 풀이를 접근해 봐야겠다!!  

 

 

 

 

 

참고 및 인용 

 

https://dev-mandos.tistory.com/346