티스토리 뷰

문제: icpc.me/1222


문제를 해석하면 만약 홍준이가 팀원의 수를 k명이라 정했다면 학교 사람의 수가 k로 나누어 떨어지는 학교만 참가할 수 있다.


즉 주어진 수들을 전부 소인수 분해를 하였을 때 i를 소인수로 가진 학교의 개수를 a[i]라고 하면, a[i]가 2이상인 경우에서의 i*a[i]의 최댓값이 답이 된다.


하지만 모든 수의 소인수를 구할 경우 O(N*sqrt(N))으로 시간내에 들어오기에는 조금 무리가 있다.


하지만 수를 받으면서 소인수를 계속 연산하는 방법이 아닌 수를 전부 받아놓고 하나의 수에는 한번의 계산만 하는 방법으로 최적화 시켜 시간내에 통과시킬 수 있다.


이보다 좋은 방법은 모든 수 i에 대하여 자신을 소인수로 가지는 수를 직접 계산해주는 방법이다. 이 방법은 소스코드로 설명을 대체한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
ll n,x,res,a[2000020];
int main(){
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",&x);
        a[x]++;
    }
    for(ll i=1;i<=2000000;i++){
        ll cnt=0;
        for(ll j=i;j<=2000000;j+=i)
            cnt+=a[j];
        if(cnt>1)
            res=max(res,cnt*i);
    }
    printf("%lld\n",res);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)11964 Fruit Feast  (0) 2018.06.25
BOJ)11046 팰린드롬??  (0) 2018.06.25
BOJ)1222 홍준 프로그래밍 대회  (0) 2018.06.25
BOJ)15675 괴도 강산  (0) 2018.06.24
BOJ)13016 내 왼손에는 흑염룡이 잠들어 있다  (0) 2018.06.24
BOJ)15673 헤븐스 키친2  (1) 2018.05.06
TAG
댓글
댓글쓰기 폼