이거 이름 다 백준 문제 제목으로 바꾸려고 하는데 이건 또 언제 바꾸나... 후... 여튼 시작!

2004: 조합 0의 개수

1. 내 풀이 1: 실패

import sys

n, m = map(int, sys.stdin.readline().split())

factorial_n = 1
for i in range(1, n+1):
    factorial_n = factorial_n * i
factorial_m = 1
for j in range(1, m+1):
    factorial_m = factorial_m * j
factorial_rest = 1
for k in range(1, n-m+1):
    factorial_rest = factorial_rest * k

combination = str(round((factorial_n/factorial_m)/factorial_rest))

result = 0
for i in range(len(combination)-1, 0, -1):
    if combination[i] == '0':
        result += 1
    else:
        break

print(result)

이전에 팩토리얼 0의 개수로 이 문제를 풀 때는 이렇게 실제 팩토리얼을 구현해도 맞았다. 그래서 이번에도 그렇게 하였으나... 결과는,

시간초과였다. 이거 말고도 math 모듈 활용해서도 한 번 해봤지만 역시나 실패.

2. 내 풀이 2: 성공

사실 완전 내 풀이라곤 볼 수 없고~ 앞에 팩토리얼 0의 개수를 풀어서 약간 어떻게 해야할지 감은 있는데 뭔가 빡! 떠오르는 게 없었다. 그래서 살짝 힌트를 얻고자 아이디어 부분만 찾아보았다.

참고한 블로그는 아래의 블로그.
https://deok2kim.tistory.com/195

코드는 다음과 같다.

import sys
n, m = map(int, sys.stdin.readline().split())
def count(i, j):
    cnt = 0
    while i != 0:
        i//= j
        cnt += i
    return cnt

five = count(n, 5) - count(m, 5) - count((n-m), 5)
two = count(n, 2) - count(m, 2) - count((n-m), 2)

if five < two:
    print(five)
else:
    print(two)

뭔가 레베루가 올라가면서 점점 풀이에 함수가 많이 쓰이는 것 같다.

여하튼, 풀이에 대해서 설명을 하자면 조합 0의 개수에서는 5의 개수와 2의 개수를 모두 세주어야 한다.

0의 개수 = 10의 배수 = 10은 2와 5로 이루어짐

이니까!

2의 개수를 세주어야 한다는 부분을 떠올리지 못한 게 참으로 아쉽다. 기존에는 count 함수에서 i를 나누는 게 5였는데, 이번에는 2나 5여야하므로 새로운 인수를 추가한다. 그리고 n과 m, n-m을 해당 함수에 넣어 구하는 것...! 따지고 보면 쉽다 ㅎㅎ

참고로 five와 two의 대소 비교를 해준 것은, 더 작은 카운트만큼 10의 배수가 만들어지기 때문이다.
ex) 2는 4개, 5는 2개 -> 2 x 2 x 5 x 5 = 100 -> 2에서 2개가 남음

사실 이번 풀이는 세모 풀이 (완벽히 내가 해낸 풀이가 아니라는 뜻임) 지만... 아이디어를 보아도 구현할 줄 몰랐던 어린 아이가 이만큼 컸다는 것에 의미부여를 하도록 하겠다... ^^

이렇게 오늘도 신기한 알고리즘의 세계 끝!