Algorithm) BOJ) 백준 1676 - 팩토리얼 0의 개수

문제보러가기

1676번: 팩토리얼 0의 개수

팩토리얼을 구하는 방법은 다들 아실텐데요,

문제는 수가 조금만 커져도 그 값이 어마어마하게 커진다는게 문제에요ㅠㅠ 

 

/

뒤에 숫자 0이 붙는다는 건 무슨 의미일까요?

/

 

2라는 숫자를 20으로 만들려면 어떻게 해야할까를 생각하면 이해가 쉬울 것 같습니다.

한 마디로 10이 곱해진다는 뜻이죠 !

즉 우리는 팩토리얼에서 10이 몇 개가 있는지를 확인하면 된답니다! 

10 = 5 x 2 이므로 5의 개수와 2의 개수를 확인하면 되겠죠?

 

/

그렇다면 2의 개수와 5의 개수는 어떻게 확인할까요?

/

 

먼저 15! 을 한번 예로 들어볼게요, 

 

1 x 2 x 3 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15

 

여기에 2와 5는 몇 개나 들어있을까요?

우선 5부터 생각해 보자구요,  5의 배수만 확인하면 되겠죠? 

5,  10,  15 

1x5, 2x5, 3x5

여기서 1, 2, 3 이 5와 곱해져,  5는 3개가 있습니다. 

 

그렇다면 25! 에는 5가 몇 개 들어있을까요?

5 10 15 20 25

1x5, 2x5, 3x5, 4x5, 5x5

여기서 1, 2, 3, 4, 5 가 5와 곱해져,  5는 5개가 있습니다.

그리고 또 5와 곱해진 ( 1 ~ 5 ) 중에서 1이 또 5와 곱해져 5는 1개가 더 있습니다.

 

규칙을 찾으셨나요? 

 

네 125를 생각해봅시다.

125에는

( 1~25 ) x 5

125는 1 ~ 25까지 5는 25개가 있습니다.

25는 1 ~ 5 까지 5는 5개가 더 있습니다.

5는 5가 1개가 더 있습니다. 

 

다시 말해서 N이라는 숫자에 5가 몇 개가 있는지 확인하기 위해서는

 

N을 5로 계속 나눠서 그 몫을 세면 됩니다. 

 

이해가 좀 되셨나요?

2도 만찬가지 방식으로 2로 계속 나눠서 그 몫을 세면 되겠죠.

하지만 여기선 무조건 5보다 2의 개수가 많기 때문에

(2의 배수가 몇 개나 될 지 생각해보면...)

5의 개수만 세면 10의 개수가 되고 뒤에 붙는 0의 개수가 됩니다 :D

 

코드로 보면

if let n = readLine().map({ Int($0) ?? 0}) {
    var num = n
    var count = 0
    if num != 0 {
        while num > 0 {
            num /= 5
            count += num
        }

        print(count)
    } else {
        print(0)
    }
}

 

다음과 같이 풀 수 있겠습니다!

 

조금이라도 도움이 되셨으면 좋겠습니다 

긴글 읽어주셔서 감사합니다 ^_____^