[백준 2904] 수학은 너무 쉬워 [C]

백준 - 2904

---

풀이

난이도에 비해 생각할 내용이 좀 많은 문제였다.

 

점수를 계산할 수들을 소수로 나누고 곱하는 과정을 통해 가장 큰 점수를 알아내는 문제이다.

즉, 입력받는 수들을 소인수분해하고, N개의 수들이 가장 큰 gcd값을 가지도록 소인수를 재분배하는 문제이다.

 

1e6까지의 78,498개의 소수들을 구하고, 입력받은 num에 대해 소인수분해를 하면서 소인수의 개수를 세주어야 한다.

다음의 예제를 보자.

백준 - 2904

 8 = 2*2*2

24 = 2*2*2 *3

 9 = 3*3

일때, N개의 수에 대해 2는 6개, 3은 3개가 존재한다.

이때 N = 3개의 수에 대해 각 수가 가져야할 인수들의 평균 개수는 2는 2개(6/N), 3은 1개(3/N)이므로, N개의 수들이 인수를 2*2*3으로 가질때가 가장 큰 gcd값이다.

 

문제에서 가장 큰 gcd값을 구하는 연산 과정은 나눈 후 곱해지는 순서이므로, n번째로 입력받은 수를 구성하는 소인수들의 개수가 평균 개수보다 작을 때의 차이의 합이 총 연산 횟수임을 알 수 있다. 

---

소스코드

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#define MAX 1000001
#define MAX_PRIME 78499
typedef struct{
    int prime, cnt;
}Prime;

Prime p[MAX_PRIME];
bool cNum[MAX];
int arr[100][MAX_PRIME];

int main(){
    for (int i = 2; i*i <= MAX; i++)
        if (!cNum[i])
            for (int j = 2*i; j < MAX; j += i)
                cNum[j] = true;

    for (int i = 2, idx = 0; i < MAX; i++)
        if (!cNum[i])
            p[idx++].prime = i;
	
    int N;
    scanf("%d", &N);
    for (int n = 0, num; n < N; n++){
        scanf("%d", &num);
		
        for (int i = 0; i < MAX_PRIME; i++){
            while (num % p[i].prime == 0){
                num /= p[i].prime;
                p[i].cnt++;
                arr[n][i]++;
            }
            if (num == 1) break;
        }
    }
	
    int result = 1, cnt = 0;
    for (int i = 0; i < MAX_PRIME; i++){
        int gcd = p[i].cnt/N;
        for (int n = 0; n < N; n++)
            if (gcd > arr[n][i])
                cnt += (gcd - arr[n][i]);
                
        result *= pow(p[i].prime, gcd);	
    }
    printf("%d %d", result, cnt);
}

---

출처

2904번: 수학은 너무 쉬워