백준 2904번 수학은 너무 쉬워 : 마포 코딩박

문제

상근이의 할머니는 매우 유명한 수학자이다. 할머니는 매일 수학 문제로 상근이를 힘들게 한다. 할머니는 종이 N장에 숫자를 하나씩 쓴 다음 상근이에게 준다. 그 다음 상근이는 다음과 같이 문제를 풀어야 한다.

두 수 A와 B를 고르고, A를 나눌 수 있는 소수 X를 고른다. 그 다음, A를 지우고 A/X를 쓰고, B를 지우고 B×X를 쓴다.

상근이는 위의 행동을 무한히 반복할 수 있다. 할머니는 상근이가 만든 수를 보고 점수를 계산한다. 점수가 높을수록 할머니는 상근이에게 사탕을 많이 준다. 점수는 종이에 적혀있는 모든 수의 최대공약수이다.

상근이가 얻을 수 있는 가장 높은 점수를 구하는 프로그램을 작성하시오. 또, 그 점수를 얻으려면 최소 몇 번 해야 하는지도 구한다.

문제풀이

사용한 알고리즘: 수학

(1) 생각

 N개 수들의 gcd 의 최대값을 구하는 문제였습니다.

 모든 수의 소인수를 모두 모아 이를 N개의 수들이 공평히 갖고 있는다는 생각합니다.
 이는 곧 모든 수들의 gcd를 이루게 됩니다.
 예를들어 8, 24, 9 인 경우,
 8 = 2^3 , 24 = 2^3 * 3, 9 = 3^2 이므로 모든 수들의 총 소인수는 2가 6개, 3이 3개 입니다.
수들이 총 N=3 이므로 각 수들은 2를 6/3=2개, 3을 3/3=1개 갖고 있을 수 있습니다.
따라서 2^2 * 3 = 12 가 총 gcd 가 됩니다.

(2) (코드: 26~31)

 수는 최대 10^6이므로 에라토스테네스의 체를 사용하여 10^3까지의 소수를 구해줍니다.
 ( 어떤 수 A 는 root(A) 이상의 소수로 나눠지지 않습니다. Root(10^6)=10^3 )

(3) (코드: 11~24)

 인수분해를 하는 함수를 만들어줍니다.

(4) (코드: 33~39) 

 N 개의 수를 받으면서 각 수를 소인수 분해하여 저장합니다.
 이때 N개의 수에 쓰인 총 소인수 또한 계산해줍니다. ( map을 사용했습니다. )

(5) (코드: 41~46) 

 gcd를 구해줍니다.

(6) (코드: 47~50) 

 각 N개의 수를 둘러보며, 갖고있어야 하는 수보다 부족한 만큼 count 해줍니다.
 ( 부족한것만 보는 이유는 N개수들이 갖고있는 총 소인수를 N빵 해주었으므로, 어떤 수가 해당 소인수를 부족하게 갖고 있다면, 어떤 수가 해당 소인수를 많이 갖고있음을 의미합니다. 많이 갖고 있는 수에서 적은 수에 해당 소인수를 준다고 생각했습니다. )

	#include <bits/stdc++.h>
	using namespace std;
	#define ll long long
	vector<int> Prime;
	bool visited[1001];
	int N, cnt;
	map<int, int> temp;
	vector<map<int, int>> arr;
	map<int, int> total;
	void Div(int a){
	for(auto now: Prime){
	if(a%now==0){
	temp[now]++;
	total[now]++;
	Div(a/now);
	return;
	}
	}
	if(a!=1){
	temp[a]++;
	total[a]++;
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	//에라토스테네스의 체
	for (int i = 2; i < 1001; ++i){
	if(visited[i]) continue;
	Prime.push_back(i);
	for (int j = 2*i; j < 1001; j+=i) visited[j]=true;
	}
	cin >> N;
	for (int i = 0; i < N; ++i){
	temp.clear();
	int num;
	cin >> num;
	Div(num);
	arr.push_back(temp);
	}
	ll ans = 1LL;
	for(auto now: total){
	int tt = now.second;
	tt/=N;
	total[now.first]=tt;
	while(tt--) ans*=now.first;
	}
	for (int i = 0; i < N; ++i)
	for(auto now: total)
	if(total[now.first]>arr[i][now.first])
	cnt+=total[now.first]-arr[i][now.first];
	cout << ans << ' ' << cnt << '\n';
	return 0;
	}

view raw BOJ 2904.cpp hosted with ❤ by GitHub