백준 온라인 저지 | 10872번 팩토리얼 | C++

백준 온라인 저지 | 10872번 팩토리얼 | C++

10872번: 팩토리얼

 

1. 문제 접근

 수학에서 팩토리얼(factorial)은 그 수보다 작거나 같은 모든 양의 정수의 곱이다. 예를 들어 N!은 N × (N-1) × (N-2) × ... × 2 × 1을 나타낸다. 재귀 문제를 풀 때 생각해야 할 함수 인자, 기본 조건, 그리고 재귀 조건을 살펴보자.

 

■ 1.1 함수 인자

 N! = N × (N-1) × (N-2) × ... × 2 × 1으로 미루어보아 팩토리얼을 계산하기 위해서 필요한 숫자는 양의 정수 N임을 알 수 있다. 그러므로 재귀 함수에 전달할 인자는 사용자가 입력할 양의 정수 N이다.

 

■ 1.2 기본 조건

 팩토리얼은 어떤 수보다 작거나 같은 모든 양의 정수의 곱이지만, 0!은 1로 별도로 정의되어 있다. 0보다 작은 숫자는 음의 정수이므로 팩토리얼을 더 이상 정의할 수 없는 숫자이므로 팩토리얼의 기본 조건(base condition)은 N이 0일 때이고 1을 반환하도록 구현해야 한다.

 

■ 1.3 재귀 조건

 N! = N × (N-1) × (N-2) × ... × 2 × 1은 N! = N × (N-1)!으로 나타낼 수 있다. 즉, 양의 정수 n에서 1만큼 감소시킨 값을 재귀 함수의 인자로 전달하여 호출한 다음, 이 재귀 함수에서 반환된 값에 n을 곱하는 방식으로 구현할 수 있다.

 

2. 문제 풀이

1. 재귀 함수 factorial을 정의한다.
   • 매개 변수로 전달할 인자는 사용자가 입력한 양의 정수인 n이다.
2. 기본 조건을 구현한다.
   • n이 0인 경우, 1을 반환한다.
3. 재귀 조건을 구현한다.
   • n이 0이 아닌 경우, n - 1을 인자로 전달한 재귀 함수를 호출한다.
   • 위 재귀 함수에서 반환된 값에 n을 곱해 반환한다.

 

3. 문제 해결

#include <iostream>
using namespace std;

int factorial(int n);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N;
	cin >> N;
	cout << factorial(N) << '\n';
	return 0;
}

int factorial(int n) {
	// 기본 조건입니다. 0!은 1입니다.
	if (n == 0) {
		return 1;
	}
	// 재귀 조건입니다. n!은 n * (n-1)!입니다.
	else {
		return n * factorial(n - 1);
	}
}

10872번 팩토리얼 성공

 

4. 문제 고찰

 팩토리얼은 가장 기본적인 재귀 함수 문제여서 쉬운 편이었다. 재귀 문제는 함수 인자, 기본 조건, 재귀 조건 이 세 가지를 올바르게 파악할 수 있도록 문제를 더 많이 풀어봐야겠다.