[Algorithm] 27. N!의 표현법

인트로

꽤나 수학적인 문제이다.

문제를 풀기 전 알아야 할 한 가지 개념이 있다.

2 이상의 모든 자연수는 소수의 곱으로 표현할 수 있다.
예를 들어 12는 2 x 2 x 3으로 표현할 수 있다.
이처럼 2 이상의 자연수는 소수의 곱으로 쪼개질 수 있다.

N!의 표현법

문제

임의의 N에 대하여 N!은 1부터 N까지의 곱을 의미한다. 이는 N이 커짐에 따라 급격하게 커진다.

이러한 큰 수를 표현하는 방법으로 소수들의 곱으로 표현하는 방법이 있다.
먼저 소수는 2, 3, 5, 7, 11, 13... 순으로 증가함을 알아야 한다. 예를 들면 825는 (0 1 2 0 1)로 표현이 가능한데, 이는 2는 없고 3은 1번, 5는 2번, 7은 없고, 11은 1번의 곱이라는 의미이다.

101보다 작은 임의의 N에 대하여 N팩토리얼을 이와 같은 표기법으로 변환하는 프로그램을 작성해 보자.
출력은 아래 예제와 같이 하도록 한다.

※ 입력설명
첫 줄에 자연수 N(3<=N<=100)이 입력된다.

※ 출력설명
소수의 곱으로 표현한다.

[참고] 없는 소수는 출력하지 않는다.

입력 #1

5

출력 #1

5! = 3 1 1

 

입력 #2

53

출력 #2

53! = 49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1

코드 설명

아주 직관적이고 단순한 해결 방법을 생각해보자.

팩토리얼 값을 계산 후 차례차례 소수로 나눠서 나누어진다면 vector의 값을 1 증가시킨다.

 

하지만 팩토리얼을 다루기 전 염두에 둘 것이 있다.

int에 담을 수 있는 팩토리얼의 최댓값은 12이다.

그만큼 팩토리얼 값은 수가 증가함에 따라 계산된 결과는 기하급수적으로 증가한다.

문제는 팩토리얼 값을 저장할 데이터 타입도 이슈가 되지만 값을 처리하는 과정도 매우 오랜 시간을 요구한다.

 

즉 팩토리얼을 다루는 문제는 팩토리얼 값 자체를 결과 도출에 사용할 일이 드물다는 뜻이다.

따라서 수학적인 사고가 필요한 문제가 대다수이다. 본 문제도 동일하다. 

 

인트로에서 언급한 2 이상의 자연수는 소수들의 곱으로 표현이 가능하다는 개념을 본 문제에 적용하면 문제풀이가 쉬워진다.

6을 예로 들어보면 5!은 1 X 2 X 3 X 4 X 5 X 6이다.

2는 소수인 2로 나뉘고 나머지가 1이다.

3은 소수인 3으로 나뉘고 나머지가 1이다.

4는 소수인 2로 나뉘고 나머지가 2이다. 다시 한번 소수인 2로 나뉘고 나머지가 1이다.

5는 소수인 5로 나뉘고 나머지가 1이다.

6은 소수인2로 나뉘고 나머지가 3이다. 2로는 더 이상 나머지를 나눌 수 없다. 3은 소수인 3으로 나뉘고 나머지가 1이다.

 

이와 같은 과정을 거치면 팩토리얼 값을 계산하지 않더라도 N!의 표현법을 코드로 구현할 수 있다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	
	cin >> n;

	vector<int> vec(n + 1, 0);

	for (int i = 2; i <= n; i++)
	{
		int temp = i;
		int div = 2;

		while (true)
		{
			if (temp % div == 0)
			{
				vec[div]++;
				temp /= div;

				if (temp == 1)
					break;
			}
			else
				div++;
		}
	}

	cout << n << "! = ";

	for (int i = 1; i <= n; i++)
		if (vec[i] != 0)
			cout << vec[i] << " ";
}

마치며

본 문제의 응용버전을 풀어보고 싶다면 N!에서 0의 개수을 참조하세요.

[Algorithm] level1 : N!에서 0의 개수