글 읽기 - java 시간초과

jyb2605 4년 전 0

안녕하세요.

자바로 조합의 결과의 소인수 분해 중 2와 5의 개수를 이용하여 문제를 풀려고 합니다.

아래는 제가 작성한 코드인데, 제출하면 0%에서 시간이 흐른 뒤 시간초과가 발생합니다.

제가 입력을 잘못받아서 그런걸까요??

import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        long N, M, two = 0, five = 0;
        N = scanner.nextLong();
        M = scanner.nextLong();

        for(long num = 1; num <= N; num++){
            long tmp = num;
            while(tmp % 2 == 0){
                tmp/=2;
                two++;
            }
            tmp = num;
            while(tmp % 5 == 0){
                tmp /= 5;
                five++;
            }
        }

        for(long num = 1; num <= (N - M); num++){
            long tmp = num;
            while(tmp % 2 == 0){
                tmp/=2;
                two--;
            }
            tmp = num;
            while(tmp % 5 == 0){
                tmp /= 5;
                five--;
            }
        }
        for(long num = 1; num <= M; num++){
            long tmp = num;
            while(tmp % 2 == 0){
                tmp/=2;
                two--;
            }
            tmp = num;
            while(tmp % 5 == 0){
                tmp /= 5;
                five--;
            }
        }

        if(two < five){
            System.out.println(two < 0 ? 0 : two);
        }else{
            System.out.println(five < 0 ? 0 : five);
        }
    }
}

bupjae 4년 전 0

소인수의 개수를 세는 것은 좋으나, 1부터 20억까지 수를 하나하나 살펴보는 방법으로는 주어진 시간내에 풀 수 없습니다.

좀 더 효율적인 방법을 생각하셔야 합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

java 시간초과

jyb2605 4년 전 0

bupjae 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말