본문 바로가기

Problem Solving/Baekjoon OJ

[BOJ 2904] 수학은 너무 쉬워

 

2904번: 수학은 너무 쉬워

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 종이에 적혀있는 수 N개가 주어진다. 수는 모두 1,000,000보다 작거나 같은 양의 정수이다.

www.acmicpc.net

 

예쁘게 구현한 것을 자랑하고 싶어 가져왔다. 관련 테크닉도 자주 쓰이는 듯 하니 기억하자.

 

더보기

최대공약수를 크게 만들려면 n개의 수에 소인수가 균등하게 분배되어야 하는 것이 자명하다. n개의 수를 모두 곱한 다음 최대한 비슷하게 다시 n개의 수로 쪼갠다고 생각해도 무방하다. 그러나 이동횟수도 구해야 하므로 처음 수는 저장해야 한다. 벡터에 모든 소인수를 저장하고, 맵에 각각의 수의 소인수분해 결과와 합친 결과를 저장한다. 그리고 모든 소인수에 대해 최대공약수와 이동횟수를 갱신해주면 답을 구할 수 있다.

 

더보기
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x;
    scanf("%d",&n);
    map<int,int> m[100];
    map<int,int> p;
    vector<int> pp;
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        for(int j=2;j*j<=x;j++){
	        if(x%j==0){
                int cnt=0;
                for(;x%j==0;x/=j) cnt++;
                m[i][j]=cnt;
                if(!p[j]) pp.push_back(j);
                p[j]+=cnt;
            }
        }
        if(x>1){
            m[i][x]=1;
            if(!p[x]) pp.push_back(x);
            p[x]+=1;
        }
    }
    int gcd=1,ans=0;
    for(int i=0;i<pp.size();i++){
        int k=p[pp[i]]/n;
        int mul=1;
        for(int j=0;j<k;j++) mul*=pp[i];
        gcd*=mul;
        for(int j=0;j<n;j++) if(m[j][pp[i]]<k) ans+=k-m[j][pp[i]];
    }
    printf("%d %d",gcd,ans);
}

'Problem Solving > Baekjoon OJ' 카테고리의 다른 글

물다이아 희자  (4) 2021.02.23
(의미 없는) Platinum I 달성  (0) 2021.02.07
Ruby V 해결 & Platinum II 달성  (0) 2021.01.22
Platinum III 달성!  (2) 2021.01.21
[BOJ 1405] 미친 로봇  (0) 2021.01.12