[Java] 공약수 게임

1. 문제 설명

아래의 규칙으로 게임이 진행된다

• 게임을 하는 참가자는 가장 먼저 자연수가 적힌 카드 N개를 받는다.
• 참가자는 자신이 원하는 횟수만큼 아래의 동작을 반복할 수 있다.
  - N개의 숫자들 중 두 개의 숫자 A와 B를 고르고 B의 약수 P를 하나 고른다.
  - 숫자 A가 적힌 카드를 반납하고 숫자 (A×P)가 적힌 카드를 가진다.
  - 숫자 B가 적힌 카드를 반납하고 숫자 (B÷P)가 적힌 카드를 가진다.
• 게임이 종료될 때 각 사람은 자신이 들고있는 카드들에 적힌 숫자들 전부의 최대공약수 만큼 점수를 획득한다.
• 위와 같은 규칙일 때 얻을 수 있는 최대의 점수를 구해보자

입력형식

첫 줄에는 처음에 주어지는 숫자 카드의 수 N이 주어진다. n = (1 ~ 100)

두 번째 줄에는 총 N개의 카드에 적혀있는 숫자가 주어진다. 처음 카드에 적혀있는 숫자는 100만이하의 자연수이다.

출력 형식

예인이가 얻을 수 있는 최대의 점수를 한 줄에 자연수로 출력한다.

2. 알고리즘 접근

게임에서 b의 약수p를 골라 a * p , b / p 를 한다는 것은 p의 소인수만큼을 a에 곱하고 p의 소인수만큼을 또 b로 나누는 것이기에 모든 카드의 소인수개수 총합은 같다.

규칙 분석

각 숫자의 약수(혹은 소인수)를 내 마음대로 이동시켜도 무관하다
결과적으로, 각 숫자를 구성하는 소인수를 알면 내 마음대로 재분배 할 수 있다

최대공약수 성질

8, 24, 50, 750을 소인수분해하면
$8 = 2 ^ 3$
$24 = 2 ^ 3 * 3$
$50 = 2 * 3^3$
$750 = 2 * 3 * 5^3$ 이다
여러 숫자의 최대 공약수는 각 소인수 p에 대해 가장 적게 존재하는 빈도 수를 곱한다
즉 위의 경우 $2^1 * 3 ^ 0 * 5^ 0$이 되어 2가 최대공약수가 된다

결과적으로 최대공약수를 최대화 하기 위해서는
각 소인수를 최소빈도로 가지고 있는 숫자의 빈도수를 높여주어야 한다
->각 소인수가 모든 숫자에 존재하는 총 개수를 안다면 자유롭게 분배 가능
즉, 각 소인수를 N개의 카드에 최대한 고르게 배분하면 최대공약수는 최대가 된다.

소인수를 고르게 배분하는 방법은 각 카드에서 n으로 나누는 것과 같다.
그 이유로는 우리가 10개를 세명한테 균등하게 나눌 때 3 3 4 위와 같이 개수에서 사람을 나누는 것과 같이 각 카드 p q r의 소인수 x y z 개가 존재한다면
최대 공약수는 $p^{x/n}q^{y/n}r^{z/n}$ 과 같다.

직접적인 구현은 소스코드를 확인

3. 소스코드

package algorithm.comon.chapter4;

import java.util.ArrayList;
import java.util.Scanner;

public class Q4J {
    static final Scanner sc = new Scanner(System.in);
    public static final int MAX_VALUE = 1000000;

    private static int getMaxiumGCD(int n, int[] cards) {
        int answer = 1;
        int[] frequency = new int[MAX_VALUE + 1];

        // 소인수분해를 한다.
        // 소인수에 대한 빈도수를 계산한다.
        for(int C: cards){
            ArrayList<Long> factors = MathUtil1.factorize(C);
            for(long f : factors){
                // 모든 소인수에 대해 빈도수 생성
                frequency[(int)f]++;
            }
        }
        // 각각의 소인수를 균등분할한다.
        for(int i = 2; i <= MAX_VALUE; i++){
            // 모든 소인수 i에 대해
            // 어차피 소인수 아니면 0이라 빈도수 스킵
             if(frequency[i] == 0) continue;

              // 균등분할 몇개씩?
            int count = frequency[i] / n;

            answer *= MathUtil1.powInt(i, count);
        }


        return answer;
    }

    public static void main(String[] args) {
        int n = sc.nextInt();
        int[] cards = new int[n];

        for(int i = 0 ; i < n; i++){
            cards[i] = sc.nextInt();
        }

        int answer = getMaxiumGCD(n, cards);

        System.out.println(answer);
    }
}
class  MathUtil1{

    public static ArrayList<Long> factorize(long n) {
        ArrayList<Long> factors = new ArrayList<>();

        for(long div = 2; div * div <= n; div++){
            while (n % div == 0){
                // 소인수 목록에 div 추가
                factors.add(div);

                // N에서 소인수만큼 나눈다
                n /= div;
            }
        }
        if(n > 1){
            // 소인수를 찾지못하고 남아있는 n이라면 반드시 소수다 이를 소인수에 추가
            factors.add(n);
        }

        return factors;

    }

    // a ^ n을 구하는 함수
    public static int powInt(int a, int n){
        int result = 1;

        for(int i = 1; i <= n; i++){
            result *= a; // a를 n번 곱한다.
        }
        return result;
    }
}