백준 15996번 파이썬 문제풀이(팩토리얼 나누기)

---

 

위 문제는 직접 적어보면 다음과 같이 나온다.

# 20!에 곱해진 2의 개수

# 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
#   1   1   1   1    1     1     1     1     1     1 #2가 곱해진 개수 5개
#       1       1          1           1           1 #2가 곱해진 개수 3개
#               1                      1	     #2가 곱해진 개수 2개

-> 즉, 처음에 2가 한개 곱해진 개수 5개이다. 추가적으로 4(2*2), 8(2*2*2) 16(2*2*2*2) 이므로 추가적으로 2가 곱해진 개수를 더해주는 식으로 구하면된다. 이런식으로 하다보면 개수를 찾을 수 있는데 여기의 개수는 20을 2나눈 개수 + 20을 2*2 로 나눈 개수 + 20을 2*2*2로 나눈개수 + 20을 2*2*2*2 로나눈 개수와 동일하다. 해당 식을 코드로 작성하면 다음과 같다.

 

N, A = map(int, input().split())

count = 0
X = A
while X <= N:
    count += N // X
    X *= A
print(count)