goorm CodingTest 큰 팩토리얼

------ 문제 ------

 

------ 풀이 ------

import java.io.*;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
int n = Integer.parseInt(input);

long result = factorial(n)%1.000.000.007;
System.out.println(result);
}

private static long factorial(int n)
{
long result=1;

for(int i = 1; i <= n; i++)
{
result = (result*i)%1.000.000.007;
}
return result;
}
}

 

------ 문제점 ------

1. 팩토리얼 알고리즘 연산 

2. 나머지 계산 

3. 오버플로우

 

------ 해결방안 ------

1. ex) 5! = 5 * 4 * 3 * 2 * 1 == 120; => n부터 n-1 일까지 , 반대로 1부터 n까지의 모든 수를 곱한 결과

2. 문제 내용처럼 1.000.000.007을 나눈 결과

3.팩토리얼은 매우 빠르게 커지기 때문에, 예를 들어 20!은 약 19경, long 타입의 최대값을 초과할 수 있어, 중간 결과를 1.000.000.007로 나눈 나머지를 취함

4. 모듈러 연산을 통해 (A*B) %m 은 (A%m)*(B%m) %m과 같으므로 오버플로우 방지를 위해 result의 값에 m으로 나누어 반환.