군대에서_코딩하기_알고리즘_13

꽤 간단하면서도, 런타임때문에 고민을 조금 해야했던 문제였다.
임의의 N(3~1000)을 받으면, 팩토리얼로 취급하여, 소인수 분해한 값을 나타내는 것이다. 예를 들어 N으로 5를 입력받으면, 5! = 1 x 2 x 3 x 4 x 5 이기때문에 3 1 1 으로 나타낸다. 또 다른 예는, 만일 N으로 825를 입력받으면 825는 1개의 3과, 2개의 5, 그리고 1개의 11로 이루어져있기 때문에 1 2 1 로 출력한다.

처음에는 단순하게 이중포문을 사용하려고 했지만, 만약 N이 1000이 될 경우, 이중포문이기 때문에 시간복잡도가 N^2이 된다. 그래서 계속해서 N을 소인수분해해주지만, N값을 계속해서 줄여줘야한다. 코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
    
    
    int N, i, j, temp;
    
    cin>>N;
    //1 2 3 4 5
    //1 2 3 2 2 5
    // 3 1 1
    vector <int> result(N+2);
    
    for(i=1; i<=N; i++){
        temp = i;
        while(temp>1){
            for(j=2; j<=i; j++){
                if(temp%j==0){
                    result[j]++;
                    temp = temp / j;
                    break;
                }
            }
        }
    }
    cout<<N<<"! = ";
    for(i=0; i<N+1; i++){
        if(result[i]!=0){
            cout<<result[i]<<" ";
        }
        
    }
}

사실 for문, while문, 그리고 다시 for문으로 총 3번의 반복문이 쓰였지만, temp라는 값을 계속해서 줄여줬기 때문에 생각보다 시간복잡도가 그렇게 높지 않다. while문을 적절하게 잘 이용할것!