[백준] 10872번 - 팩토리얼 (Java)

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

10872번: 팩토리얼

 

 

<문제 분석>

팩토리얼은 그 수 보다 작은 모든 정수의 곱이다.

5! = 5 x 4 x 3 x 2 x1이다.

즉, n! = n x (n-1)!과 동일하다.

이를 재귀함수로 구성하자.

 

 

<코드 구현>

import java.util.*;
import java.io.*;

/*
[백준] 10872번 - 팩토리얼 (Java)
*/

public class Main {
    static int N;

    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
    }

    // 재귀함수로 풀기
    long factorial(long n) {
        if (n <= 1) return 1; // (n == 1)일때 runtime error 발생!

        return n * factorial(n-1);
    }

    // 반복문으로 풀기
    long loop(int n) {
        long sum = 1;
        while (n > 0) {
            sum = sum * n;
            n--;
        }
        return sum;
    }
    
    void Solve() throws Exception {
        //long ans = factorial(N);
        long ans = loop(N);
        System.out.println(ans);
    }

	public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<제출 결과>

 

<풀이 후기>

재귀함수의 가장 기본적인 문제라서 너무 쉽게 구현을 한 것이 실수였다. 계속 런타임 에러가 발생했는데 원인 파악이 바로 안되었다. 알고보니 리턴 타입을 int가 아닌 long으로 해줘야 했고, 재귀함수 종료조건을 if (n==1)이 아닌 if (n<=1)으로 해주고서야 맞출 수가 있었다. 왜냐하면 0!도 1이기 때문이다.

 

재귀함수는 언제난 반복문으로 풀 수 있다. 반복문으로 변경해서 풀이하는 연습도 병행하자.