백준 알고리즘 10872번: 팩토리얼 C언어

문제 출처: www.acmicpc.net/problem/10872

10872번: 팩토리얼

1. 코드

#include <stdio.h>

int fac(int n)
{
    if(n > 1) return n * fac(n - 1);
    else if(n == 0) return 1;
    else return n;
}
int main(void)
{
    int N;
    
    scanf("%d", &N);
    printf("%d", fac(N));
    return 0;
}

2. 문제 해결 방식

제목이 팩토리얼에 관한 것이니 우선 팩토리얼에 대해서 먼저 알아보자.

n!= n × (n − 1) ⋯⋯ × 3 × 2 × 1 (단, n ≥ 0)

팩토리얼은 n!으로 표시하는데 간단히 이야기하면 n에서 1씩 뺀 값들을 하나씩 곱한 것이다.

예시로 6! = 6 × 5 × 4 × 3 × 2 × 1이다. 그리고 이것을 재귀 함수로 구현할 것인데 재귀 함수란, 이미 실행된 함수에서 스스로 필요한 만큼 호출하는 것을 말하는데 다음 그림을 참고해보자.

 

재귀함수

 

이러한 방식으로 특정 한 함수가 호출되어 실행이 완료되어도 스스로 다시 호출하는 것을 말한다. 그렇다면 스스로를 호출하면서 n - 1씩 뺀 값을 계속해서 재귀 함수를 통해 n * (n - 1)를 구현하면 된다.

하지만 이렇게만 작동시키면 아마 틀릴 것이다. 왜냐하면 다시 처음으로 돌아가서 팩토리얼은 3!, 2!, 1! 등이 있지만 조건을 보면 n ≥ 0이다. 즉, 0! 또한 될 수 있다는 것이다. 0! = 0 일까? 전혀 아니다. 그 이유에 대해 같이 알아보도록 하자.

 

팩토리얼 예시 (1)

 

3! 를 예시로 들었는데 팩토리얼을 나열하면 이렇게 변한다. 그렇다면 1! 은 어떻게 구성되어 있는지 다음 그림을 참고하기 바란다.

 

팩토리얼 예시 (2)

 

팩토리얼 예시(1)를 보면 1! 의 값이 1이라는 것을 알 수 있다. 그렇다면 1! 를 전개하면 0! 또한 1이 된다는 것이다. 그렇다 0! = 1이라는 것은 어떻게 보면 팩토리얼을 구성하기 위한 조건이다.

그래서 0! = 1이라는 값을 인지하고 있다면 문제는 쉽게 해결할 수 있다.