🙏 27. N!의 표현법

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비 - 인프런 | 강의

모든 문제에 대한 저작권은 위 강의에 있습니다.

문제

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

출력 설명

소수의 곱으로 표현한다.

입력 예제 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

제출 코드

2023년 2월 14일

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N = 0;
    cin >> N;
    
    vector<int> store(N + 1);
    
    for(int i = 2; i <= N; i++)
    {
        int temp = i;
        int divide = 2;
        while(temp > 1)
        {
            if(divide > i)
                break;
            
            if(temp % divide == 0)
            {
                temp /= divide;
                store[divide]++;
            }
            else
                divide++;
        }
    }
    
    cout << N <<"! = ";
    
    for(int i = 0; i < N + 1; i++)
    {
        if(store[i] == 0)
            continue;
        
        cout << store[i] << ' ';
    }
    
    return 0;
}

풀이

숫자를 계속해서 나눠주기 위해 while문을 사용했다.