27. N!의 표현법

이 문제의 저작권은 인프런 강의 "it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비" 에 있습니다.

 

 

 

 

문제 25

 

임의의 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<=1000)이 입력된다.

 

 

 

입력예제

 

5

 

 

출력예제

 

5! = 3 1 1

 

 

 

 

---

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
	freopen("input.txt", "rt", stdin);
	int i, j, n, tmp;
	
	scanf("%d", &n);
	vector<int> ch(n+1);
    
	for(i=2; i<=n; i++){
		tmp=i;
		j=2;
		while(1){    // 소인수분해 알고리즘
			if(tmp%j==0){
				tmp=tmp/j;
				ch[j]++;
			}
			else j++;
			if(tmp==1) break;
		}
	}
	printf("%d! = ", n);
	for(i=2; i<=n; i++){
		if(ch[i]!=0) printf("%d ", ch[i]);
	}
	return 0;
}

 

(수학적 이해)

먼저 예제와 같이 설명해보면 5!과 같은 경우, 5 * 4 * 3 * 2 * 1 =120 이다.

이는 소인수가 5(5), 4(2*2), 3(3), 2(2) 와 같은 결과이고 결국 120을 소인수분해 하거나 팩토리얼을 적용해서 나온 숫자들의 각 소인수를 구하는 것이나 소인수들은 동일하게 나온다.

 

 

 

(코드 설명)

for문 안에서 tmp=i 로 치환하는 이유는 i 를 계속 쪼개야 하는데 i 를 쪼개면 for문의 i++ 에 영향을 받을 수 있다. 그래서 tmp=i 로 치환하여 tmp 를 쪼개주는 것이다. (tmp 가 소인수분해 대상이다)

 

while 문은 소인수분해 하는 과정이다. 참고로 4로 나누어떨어지는 것들은 2로도 나누어 떨어진다고 볼 수 있다. 그래서 j 는 2, 3, 5, 7... 과 같은 소인수만 남게 되는 것이다.