[BOJ] 2004번 조합 0의 개수 / 사용언어 : 파이썬(python)

※ 문제링크 

2004번: 조합 0의 개수

해당 문제는 조합의 수를 구하는 공식을 활용해서 풀어야하는 문제였다. 팩토리얼을 쓰면 무조건 시간초과 또는 메모리 초과가 뜰 것으로 예상했기에 다른 방식으로 풀어야 한다고 생각했다. 처음에 생각한 방식은 곱해야하는 수들을 리스트로 받은 후 하나하나씩 2의 개수와 5의 개수를 세고 최솟값을 반환하여 나눠주는 것이었는데 해당 방식도 곱할 수들을 하나하나 모두 세어야 했기에 메모리 초과가 발생했다. 그래서 다른 방법을 고민해보던 중 해당 숫자를 2의 배수와 5의 배수로 나누어 주면 보다 간단하게 2의 지수의 개수와 5의 지수의 개수를 구할 수 있다는 것을 알게 되었고, 해당 방식으로 문제를 해결하였다. 구체적인 문제풀이 방법과 코드는 아래와 같다.

1. 입력값을 받아서 각각의 2의 배수와 5의 배수로 나누어 줘서 2와 5의 지수의 개수를 구한다.

2. 2의 지수의 개수와 5의 지수의 개수를 각각 구한 후 그 중 작은 값을 출력한다.

+ 예시) 10을 2의 배수로 나누어 주면, 10 // 2 = 5(2, 4, 6, 8, 10), 10 // 4 = 2(4, 8) // 10 // 8 = 1(8)

   10까지의 수들이 가지는 2의 지수 : 8

 

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

def two_count(number):
    two_cnt = 0
    while number != 0:
        number = number // 2
        two_cnt += number
    return two_cnt

def five_count(number):
    five_cnt = 0
    while number != 0:
        number = number // 5
        five_cnt += number
    return five_cnt

two_cnt = two_count(N) - two_count(N - K) - two_count(K)
five_cnt = five_count(N) - five_count(N - K) - five_count(K)
print(min(two_cnt, five_cnt))

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.