백준 BOJ 2904 수학은 너무 쉬워

이 문제는 각각의 수를 소인수분해하여

각각의 숫자들이 소인수를 잘 나눠 가지면 답을 구할수 있다.

 

예제에서 8 24 9 가 주어졌는데

8 - 2 2 2 

24 - 2 2 2 3

9 - 3 3 

 

2가 6개 3이 3개 이를 잘 나눠가지면

각 숫자들이 2 2 3  =  12 가 될 수 있다.

 

즉, 각 소인수를  " 소인수의 총 개수 / 주어진 n " 으로 나눠가지면 가장 큰 점수를 구할 수 있다.

 

그 과정은 다음과 같다.

1. 소수체크를 해준다.

2. 각 숫자를 소수로 나눠주며 총 소인수 개수를 count해준다.

3. 각 숫자당 소인수와 그 개수를 알아야 최소 몇번만에 가능한지 알 수 있다.

이를 어떻게 세야할지 고민하다가 map을 n개만큼 배열로 선언하여 세어주었다.

(1,000,000 * 100 의 배열을 하면 메모리가 터지기 때문에.. )

 

최소횟수의 count를 해줄땐 각 숫자당 부족한 소인수의 개수만큼을 세주면 된다.

 

  

#include<iostream>
#include<memory.h>
#include<vector>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<string>
#include<cmath>
#define INF 1e9
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
int n, m, k;
 
int a[101];
bool chk[1000001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    memset(chk, false, sizeof(chk));
    for (int i = 2; i <= sqrt(1000000); i++) {
        if (!chk[i]) {
            for (int j = 2 * i; j <= 1000000; j += i) chk[j] = true;
        }
    }
 
    
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    
    
 
    unordered_map<int, int> mp;
    unordered_map<int, int> mpp[100];
    for (int i = 0; i < n; i++) {
        int tmp = a[i];
        
        while (tmp > 1) {
            for (int j = 2; j <= tmp; j++) {
                if (!chk[j] && tmp%j==0) {
                    if (mp.count(j) == 0) {
                        mp[j] = 1;
                        mpp[i][j] = 1;
                    }
                    else {
                        mp[j]++;
                        mpp[i][j]++;
                    }
                    tmp /= j;
                    break;
                }
            }
        
        }
    }
 
    int ans = 1;
    int cnt = 0;
    for (int i = 2; i <= 1000000; i++) {
        if (chk[i]) continue;
        if (mp.count(i) == 0) continue;
        ans *= (pow(i,(mp[i] / n)));
        if ((mp[i] / n) == 0) continue;
        for (int j = 0; j < n; j++) {
            if (mpp[j].count(i) == 0) cnt+=(mp[i]/n);
            else if ((mp[i] / n) > mpp[j][i]) {
                cnt += (mp[i] / n) - mpp[j][i];
            }
 
        }
    }
 
    printf("%d %d\n", ans, cnt);
 
    return 0;
}