[백준] 2004 조합 0의 개수

문제보기

단순히 소인수 중 2의 갯수, 5의 갯수를 순차탐색해서 세어주면 될거라고 생각했지만 시간초과 ㅠㅠ

질문게시판 찾아보며 겨우겨우 풀었다.

어떤 공통되는 소인수를 한꺼번에 제거 제거 해가며 한줄씩 밑장빼기 해준다는 느낌으로 진행한다.

import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();

    if( n == m || m == 0 ){
      System.out.println(0);
      return;
    }

    int l = n-m;

    int cnt5 = 0;
    int cnt2 = 0;

    for(long i = 5 ; n/i >= 1 ; i *= 5) {
      cnt5 += n/i;
    }
    for(long i = 5 ; m/i >= 1 ; i *= 5) {
      cnt5 -= m/i;
    }
    for(long i = 5 ; l/i >= 1 ; i *= 5) {
      cnt5 -= l/i;
    }

    for(long i = 2 ; n/i >= 1 ; i *= 2) {
      cnt2 += n/i;
    }
    for(long i = 2 ; m/i >= 1 ; i *= 2) {
      cnt2 -= m/i;
    }
    for(long i = 2 ; l/i >= 1 ; i *= 2) {
      cnt2 -= l/i;
    }

    System.out.println(Math.min(cnt2, cnt5));		
  }

}