[Inflearn] N!의 표현법(소인수분해 응용)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand the problem

  2. Redefine the problem + abstract

     - 큰 수를 소수들의 곱으로 표현

     - 소수 2, 3, 5, 7, 11 ... 이 있을 때, 825는 (0 1 2 0 1) 로 표현 가능

       이는 2는 없고, 3은 1번, 5는 2번, 7 없고, 11 1번의 곱

  3. Create a solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 우선 N 최대가 1000 이므로 1000까지의 소수를 먼저 구해보자.

     2 3 5 7 11 13 ...  이 방법은 굳이 필요 없는 듯 하다.

     N = 5, 라면

     5, (2, 3) 으로 나눌 수 없고 5로 나눠지므로 5에 해당하는 index에 ++ 

     4, 2로 바로 나눠지므로 2에 해당하는 index에 ++, 단 1이 될 때까지 나눠줘야 하므로, 다시 2로 나누면 index++

     3, 3으로 바로 나눠지므로 3에 해당하는 index++

     2, 2에 해당하는 index++

  

     결국 펙토리얼에 포함되는 숫자들을 소인수분해해주는 꼴이다.

     

    index : [0 1 2 3 4 5]

                   3 1 0  1 

    이제 cnt 정보를 담은 배열을 출력해주면 될 것 같다.

    그런데 중간에 0 이 포함되어있으므로 출력할 때 소수인지 확인한 후 소수일 경우에 출력해주어야 할 것 같다.

    아무리 큰 소인수가 있더라도 N 보다는 작거나 같은 것이다.  

    예를 들어 N이 37이라면 가장 큰 소인수는 37이 될 터이니말이다..

    사실 확실하지 않아서 불안하지만.. 한 번 코드로 옮겨볼까..?

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, i, j;
 
    scanf("%d", &n);
    vector<int> v(n+1);
 
    for (i = n; i >= 2; i--)
    {
        int num = i;
 
        for (j = 2; j <= n; j++)
        {
            while(num % j == 0)
            {
                v[j]++;
                num /= j;
            }
 
            if (num == 1)
                break;
        }
    }
 
    printf("%d! = ", n);
 
    bool isPrime;
 
    for (i = 2; i <= n; i++)
    {
        isPrime = true;
 
        for (j = 2; j < i; j++)
        {
            if (i % j == 0)
            {
                isPrime = false;
 
                break;
            }
        }
 
        if(isPrime)
            printf("%d ", v[i]);
    }
 
    puts("");
 
    return 0;
}

우선 주어진 testcase는 모두 통과했다.

하지만 코드가 길어지면 왜이렇게 주먹구구식으로 짠 것 같은 느낌이 드는지..

#. Other code

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(){
    int n, i, j, 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){
                ch[j]++;
                tmp=tmp/j;
            }
            else j++;
 
            if(tmp==1) break;
        }
    }
 
    printf("%d! = ", n);
 
    for(j=2; j<=n; j++)
        if(ch[j]!=0) printf("%d ", ch[j]);
    
    return 0;
}
                
        
    

line 13~26 에서 for문을 한 개만 사용해서 해결하였다. 나는 이중 for문을 사용했는데.. 

다시 보면 이중 for문을 쓸 필요가 없는데.. n까지 갈 일도 없고 하핳. 그래도 중간에 break를 해줘서 다행이지만..

for문이 이중으로 있다는 것 만으로 굉장히 무거워 보인다. 

중간에 break 로 반복문을 중간에 끊어낼 수 있다면 위 코드처럼 for문을 사용하지 않고 증가연산자로만으로 해도 좋을 것 같다. 

for문 자체가 돌아가면서 또 다른 연산들을 수행하기 때문에 가능하면 반복문을 안 쓰고 해결하는 방법도 중요하다.

line 30~31 출력 부분에서도 나는 소수만 걸러서 출력하려고 소수검사까지 해주었는데

소인수분해의 정의 자체가 "합성수를 소수의 곱으로 나타내는 방법"이라고 되어있는 것을 보면 굳이 소수검사는 필요가 없던 것이다..!

결국은 0이 아닌 수만 출력하면 됐었다.. 허무하다.. ㅋㅋㅋ 좋은 깨달음이었다..

#. Result

  - Input --------------------------------------------------------

5

------------------------------------------------------------------

  - Output --------------------------------------------------------

5! = 3 1 1

------------------------------------------------------------------