[BOJ 2904 // C++] 수학은 너무 쉬워

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2904번 문제인 수학은 너무 쉬워이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/2904 

2904번: 수학은 너무 쉬워

주어진 총 N개의 수를 이루는 각 소인수가 총 몇 개씩 있는지를 구하고, 이를 균일하게 분배하는 것으로 "가장 높은 점수"를 구할 수 있다.

 

이러한 "가장 높은 점수"를 만들기 위해, 각 칸마다 "부족한 소인수"를 어딘가에 있을 남는 소인수를 옮겨오면(그 수에서 해당 소인수를 나누고 소인수가 부족한 수에 곱하면) 되므로, 각 N개의 수마다 "가장 높은 점수"의 배수가 되기 위해 필요한 소수의 개수를 구해 더한 것이 "가장 높은 점수"를 얻기 위해 필요한 최소 행동 횟수가 된다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

bool sieve[1000000];
vector<int> primes;
int num[100];
int cnt[1000000];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	sieve[0] = sieve[1] = 1;
	for (ll i = 2; i < 1000000; i++) {
		if (sieve[i]) continue;
		primes.push_back(i);
		for (ll j = i * i; j <= 1000000; j += i) {
			sieve[j] = 1;
		}
	}

	int N; cin >> N;

	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		num[i] = x;
		int idx = 0;
		while (x > 1) {
			if (x % primes[idx] == 0) {
				x /= primes[idx];
				cnt[primes[idx]]++;
			}
			else idx++;
		}
	}
	int ans = 1;
	for (int i = 2; i < 1000000; i++) {
		int temp = cnt[i] / N;
		while (temp--) {
			ans *= i;
		}
	}

	cout << ans << ' ';
	
	int anscnt = 0;
	for (int i = 0; i < N; i++) {
		int x = num[i], y = ans;
		int idx = 0;
		while (y > 1) {
			if (y % primes[idx] == 0) {
				y /= primes[idx];
				if (x % primes[idx] != 0) anscnt++;
				else x /= primes[idx];
			}
			else idx++;
		}
	}

	cout << anscnt;
}