백준 #27434번 팩토리얼 3

import java.util.Scanner;
import java.math.BigInteger;
public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		System.out.println(fact(1, n));
		
		sc.close();
	}
}

위 코드로 제출하면 시간 초과가 나와 오답으로 처리 된다.
팩토리얼을 반으로 나누어 계산한 후에 곱하는 방법으로 처리해야 시간 초과가 나오지 않는다.
팩토리얼을 반으로 나누어 계산한 후에 곱하는 방법으로 짠 코드는 다음과 같다.

import java.util.Scanner;
import java.math.BigInteger;
public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		System.out.println(fact(1, n));
		
		sc.close();
	}
	
	public static BigInteger fact(int a, int n) {
		
		BigInteger mul = BigInteger.valueOf(a);
		
		if(a < n) {
			int b = (a + n) / 2;
			mul = fact(a, b).multiply(fact(b + 1, n));
		}
		
		return mul;
	}
}