ACMICPC 2004 조합

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

문제

nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다.

출력

첫째 줄에 0의 개수를 출력한다.

으으...입력 값의 크기가 너무 크다..!! 구하려는 것도 팩토리얼인데..

사실 처음 짠 코드는 그런 거 상관없고 문제만 풀리면 장땡..! 이라는 식으로 만든 코드다.

nCm = n!/{m!(n-m)!} 이라는 수식에만 맞춰서

파이선으로 심지어 팩토리얼을 구현하여 시간초과가 뜰 것이 어쩌면 당연한 코드다.

#2004 조합 from math import factorial c = 1; n, m = [int(x) for x in input().split()]; for i in range(m): c = c*n; n = n-1; c = int(c/factorial(m)); cstr = str(c); zero = 0; for s in cstr[::-1]: if (s == '0'): zero += 1; else: break; print (zero);

결국 올바른 풀이법은..

굳이 nCm의 값을 구할 필요가 없다는 거다.

필요한 것은 뒤에 오는 0의 개수이니 값을 소인수 분해해서 2 와 5의 지수중 더 작은 값을

찾아주면 그게 10^k 이겠지!

이를 위해 필요한게 nCm의 값에 2와 5가 몇 개나 들어가 있냐이고..

물론 인터넷 서핑으로 알아냈다. 수학과는 담을 쌓은지 좀 오래되서...

#2004 조합 # nCm = n!/{m!(n-m)!} def FindExponent(val, exponent): numOfExponent = 0; num = exponent; while (num <= val): numOfExponent += int(val/num); num *= exponent; return numOfExponent; n,m = [int(x) for x in input().split()]; numOfTwo = FindExponent(n, 2) - FindExponent(m, 2) - FindExponent(n-m, 2); numOfFive = FindExponent(n, 5) - FindExponent(m, 5) - FindExponent(n-m, 5); exponentTen = min(numOfTwo, numOfFive); print (exponentTen);

여담이지만, 좋은 프로그래머는 좋은 변수명, 함수명을 사용하는 프로그래머라는데

난 글러먹은걸까... 군대에서 영어공부도 해야하나..