[C++/알고리즘] 백준 10872 (팩토리얼)

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

10872번: 팩토리얼

 

팩토리얼은 자연수 n을 이용하여 기호로는 간단하게 n!로 나타내며 1부터 n까지의 자연수를 모두 곱하는 것을 의미한다. 

 

n! = n x (n-1) x (n-2) x .... x 3 x 2 x 1

 

이 정의를 이용해 재귀함수를 호출해주면서 구하면 된다. 

 

ex ) n = 5일 때

fac(5) => fac(4) * 5

fac(4) => fac(3) * 4

fac(3) => fac(2) * 3

fac(2) => (fac(1) == return 1) 1 * 2

 

그러면 5*4*3*2*1이 된다. 

 

여기서 헷갈릴 수 있는 부분은 0! 일 때이다.

0!은 0이 아닌 1이다. 

아무것도 안 더하면 0이듯이 아무것도 안 곱하면 1이기 때문이다. 

0!은 1부터 0까지 자연수를 곱하는 것이기 때문에 아무것도 곱하지 않아서 그대로 1이 나온다고 한다. 

 

 

#include <iostream>

using namespace std;


int fac(int n)
{
	if (n == 1 || n == 0) return 1;
	return fac(n - 1) * n;

}
int main()
{

	int T;
	cin >> T;

	cout << fac(T);

}

 

#include <iostream>

using namespace std;


int fac(int n)
{
	return n == 0 ? 1 : n*fac(n-1) ;
}
int main()
{

	int T;
	cin >> T;

	cout << fac(T);

}

 

예상치 못한 실수

간단하게 생각했던 문제에서 시간 초과 에러가 발생하여 당황했다.

찾아보니 n이 0일 때의 조건을 주지 않아서 시간초과가 발생했던 것이었다.

그러면서 0!이 1이라는 것도 알았다. 

당연히 당연히 0을 곱한다고 생각하고 있었던 것 같다. 

더 꼼꼼히 문제를 푸는 연습을 해야 할 것 같다. 

 

 

 

출처 

팩토리얼 https://namu.wiki/w/%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC

팩토리얼 - 나무위키