[백준] 10872 팩토리얼

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

10872번: 팩토리얼

 

내가 알고 있는 팩토리얼 해결방법은 크게 3가지이다.

1. Recursion (현재 10872번 문제분류, 풀이1)

2. Iteration (단순 반복문 구현, 풀이2)

3. DP (풀이3)

 

사실 이 문제 같은 경우에는 n의 최대값이 12로 고정되어 있어서 시간에 대한 차이가 크게 없었다. 하지만 아마도 n의 최대값이 늘어나면 늘어날수록 dp를 사용한 방법이 훨씬 효율적이고 정확하다고 생각된다. 그 이유는 2가지이며, 다음과 같다.

 

1. DP vs Iteration

 - Iteration의 경우 반복문을 돌 때 인덱스를 보통 임시변수에 곱해서 팩토리얼을 구하는 데, 이 때의 인덱스는 int형태이므로 숫자의 표현범우에 있어 제한적이다.

 - DP는 배열 자체를 long으로 설정이 가능하기 때문에 어느정도의 커버가 가능하다.

 

2. DP vs Recursion

 - Recursion을 사용하는 방법은 사실 지역변수, 힙 등의 메모리를 상당히 많이 차지하기 때문에 치명적인 단점이 있다.

 - DP의 경우 전체 공간복잡도는 O(n), 시간복잡도 역시 O(n) 안에 처리가 가능하다.

 

---

문제 및 입출력

 

---

코드

import java.util.*;

public class Main 
{
    // 재귀를 이용한 팩토리얼 구하기
    public static int facto(int n)
    {
        if(n<=1)
        {
            return 1;
        }
        else
        {
            return n * facto(n-1);
        }
    }
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = 1;
        
        // 반복문을 이용한 팩토리얼 구하기
        for(int i=2; i<=n; i++)
        {
            result *= i;
        }
        
        // dp를 이용한 팩토리얼 구하기
        int[] dp = new int[n+1];
        
        if(n<2)
        {
            System.out.println(1);
            return;
        }
        
        dp[0] = dp[1] = 1;
        
        for(int i=2; i<dp.length; i++)
        {
            dp[i] = dp[i-1] * i;
        }

        System.out.println(dp[n]);
        //System.out.println(result);
        //System.out.println(facto(n));
        
        sc.close();
    }
}

 

---

결과 비교