어려움

백준 2004 풀이 (조합 0의 개수)

진짜 개어려웠다. 처음에는 저번에 DP로 조합 푼거 생각나서 그러한 방식으로 풀면 되나 싶었는데 조건으로 나오는 값이 너무 컸다. DP로 풀어도 분명히 시간 초과날게 뻔했다. 그래서 이것저것 뒤져봐도 안되서 DP로 풀었더니 아니나 다를까 시간초과가 났다. 그래서 고수들이 푼 방식을 슬쩍 훔쳐봤다. 슬쩍 봤더니 0이 나오기 위해서는 조합의 결과안에서 2와 5가 한쌍으로 나와야 끝자리에 0이 생성된다. 따라서 해당 값의 결과에 2와 5의 개수가 몇개나 나오는지 확인해야한다. 처음에는 고수의 코드를 보고도 이해가 안갔다. 5!에 2와 5가 몇개 있는지 보려면 5!을 구하고서 2나 5로 나누면 되는거 아닌가? 라는 생각도 했다. 그런데 고수들은 5를 2로 나눠서 구하거나 5를 5로 나눠서 구하고 있었다.......