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

📔문제

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

---

📝입력

첫째 줄에 정수 N(0 ≤ N ≤ 100,000)이 주어진다.

---

📺출력

첫째 줄에 N!을 출력한다.

---

📝예제 입력 1

10

---

📺예제 출력 1

3628800

---

📝예제 입력 2

0

---

📺예제 출력 2

1

---

🧮알고리즘 분류

• 수학
• 사칙연산
• 임의 정밀도 / 큰 수 연산

---

📃소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Scanner;

public class Code27434 {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.valueOf(br.readLine());

        System.out.println(fact(1,N));
    }
    public static BigInteger fact(int a,int n){
        BigInteger ret=BigInteger.valueOf(a);

        if(a<n){
            int b=(a+n)/2;
            ret=fact(a,b).multiply(fact(b+1,n)); //두개로 나눠서 풀이
        }
        return ret;
    }
}

---

📰출력 결과

---

📂고찰

시간초과가 발생해서 파이썬으로 푼 다음, JAVA의 풀이 코드를 확인했다.

확인해보니 a<n인 동안 (만약 a==n 즉, a가 1이거나 a가 0이면 1을 리턴할 수 있도록)만 fact(a,b)와 fact(b+1,n)로 계산하였다.

fact(a,b)와 fact(b+1,n)을 계산한 후 곱해주는 건 즉 두개를 분할 정복하는 것과 비슷하다고 볼 수 있다.