[BOJ_Gold3] - 2904 수학은 너무 쉬워 [python]

 

 

2904번: 수학은 너무 쉬워

 

문제

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

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

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

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

입력

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

출력

첫째 줄에 상근이가 얻을 수 있는 가장 큰 점수와 최소 몇 번 만에 그 점수를 얻을 수 있는지를 출력한다. 

 

---

개인적으로 이름이 굉장히 맘에 안드는 문제였습니다. (ㅡ^ㅡ)

 

 

 

0~주어진 숫자들 중 가장 큰 수 까지에 대한 소수배열을 에라토스테네스의 채를 이용해 먼저 구합니다.

 

이후, 각 숫자가 어떤 소수 X의 몇승으로 이루어지는지에 대한 합을 전체 숫자의 개수로 나눈 몫을 M이라고 하면,

모든 숫자는 $X^M$을 인수로 가질 수 있습니다.

 

또한, 어떤 숫자가 M개보다 적은 X로 이루어져있다면, 부족한 만큼 다른 수에서 가져와야 하고, 이 숫자를 K라고 하면,

모든 숫자에 대한 K의 합이 모든 수가 $X^M$을 인수로 가지기 위해 필요한 이동 횟수임을 알 수 있습니다.

 

이렇게 모든 소수에 대해 위의 연산을 수행했을 때,

모든 $X^M$의 곱이 가능한 최대 공약수, 모든 Sum(K)들의 합이 그때의 최소 횟수임을 알 수 있습니다.

 

 

 

from typing import List
from math import sqrt

def getPrimes(limit : int) -> List[bool]:
    isPrime = [True] * (limit + 1)
    isPrime[0] = isPrime[1] = False

    for i in range(2,int(sqrt(limit)) + 1):
        if not isPrime[i]: continue

        for n in range(i * i, limit + 1, i):
            isPrime[n] = False
    return [i for i in range(limit + 1) if isPrime[i]]

n = int(input())
numList = list(map(int,input().split()))

primeNumbers = getPrimes(max(numList))
totalMovement = 0
totalMax = 1

for v in primeNumbers:
    totalCount = 0
    powCount = []

    for num in numList:
        count = 0
        while num and num % v == 0:
            count += 1
            num //= v
        powCount.append(count)

    avg = sum(powCount) // n

    totalMax *= pow(v, avg)  # v^avg만큼 취할수있음

    for value in powCount:
        totalMovement += avg - value if avg > value else 0 #이동이 필요한 경우

print(totalMax,totalMovement)