[파이썬/python] 백준 - 2904 수학은 너무 쉬워

문제

https://www.acmicpc.net/problem/2904

---

문제 설명

1. 숫자가 적혀있는 N장의 종이가 존재한다.
2. 두 개의 숫자 A와 B를 고르고, A를 나눌 수 있는 소수 X를 고른다. 그 다음 A를 지우고 A/X를 쓰고, B를 지우고 B*X를 쓴다.
3. 위 행동을 무한으로 반복이 가능할 때, 만든 수를 보고 점수를 계산한다. 점수는 종이에 적혀있는 모든 수의 최대공약수다.
4. 얻을 수 있는 최대 점수와 그에 필요한 연산 횟수를 구한다.

 

---

풀이

문제를 읽어보니 소수, 최대공약수.. 이런 수학적인 용어들이 많이 나오길래 문제를 수학적으로 접근했다.

먼저 간단한 예시를 통해 문제에서 요구하는 행동을 분석해보자.

 

예제 입력 2번으로 [8, 24, 9]배열이 주어진다.

$A = 8$, $B = 24$ 를 선택했다.

$A$를 나눌 수 있는 소수 $X = 2$이다. 따라서 $A/X, B*X$를 계산하면, $A = 8/2 = 4, B = 24*2 = 48$이다.

 

여기까지 계산했을 때, 한 가지를 깨달았다. 바로 한 번의 연산을 진행하면 A가 가진 소수가 B로 이동한다는 것이다.

 

좀 더 명확하게 이해하기 위해 소인수분해를 진행한 후 연산을 진행해보겠다.

$A = 2^3$, $B = 2^3*3$이다. 이전과 마찬가지로 $A/X, B*X$를 진행하면 $A = 2^2$, B = 2^4*3$이다.

A에서 2가 오른쪽으로 이동한 것을 볼 수 있다.

 

문제에서 연산이 어떻게 진행되는지 이해했다. 그럼 최고 점수는 어떻게 계산해야 할까?

 

점수는 종이에 적혀있는 모든 수의 최대공약수이다. 위 예제를 통해 점수가 어떻게 나오는지 구해보자.

[8,24,9] 배열에서 몇 번의 연산을 통해 결과를 구해보자.

1. $A = 8, B = 9, [4, 24, 18]$

2. $A = 24, B = 18, [4, 12, 36]$

3. $A = 36, B = 4, [12, 12, 12]$

최대 공약수는 12, 연산 횟수는 3회이다.

 

$[2^3, 2^3*3, 3^2]$ 배열에서 각각 12가 나오게 되려면 아래의 연산이 필요하다.

1. 1번 숫자에서 2가 3번 숫자로 이동

2. 2번 숫자에서 2가 3번 숫자로 이동

3. 3번 숫자에서 3이 1번 숫자로 이동

 

위에서 계산한 연산과 비교해보면 두 연산이 일치하는 것이 이제 눈에 보인다.

 

최대공약수는 모든 수에 공통적으로 약수가 존재해야한다. 즉 배열에서 소인수분해를 진행했을 때 숫자가 몇 번씩 등장하는지를 판단한 후 전체 개수로 나누게 되면 최대공약수를 만들기 위해 필요한 약수의 개수가 나오게 된다.

 

각각 수를 계산해서 각각 나누게 되면 그 수가 최고 점수이고, 숫자를 이동시킨 횟수가 연산 횟수가 된다.

 

지금까지 접근했던 문제들과 전혀 다른 방식이라 풀이하기 어려운 문제였다. 새로운 접근 방식을 알게되어 굉장히 유익했다. 

1. 소인수분해를 진행하여, 각각 숫자가 몇 번 등장하는지 해시를 통해 저장한다.
   1. 이 때 에라토스테네스를 사용하면 더 빠르게 계산이 가능하다. ($Nlog{logN}$)
2. 등장한 숫자들을 순차 탐색하며 N으로 나누었을 때 1보다 크거나 같다면 결과 값에 저장하고 이동에 필요한 횟수를 계산한다.
3. 결과를 출력한다.

---

코드

import sys
from math import isqrt
input = sys.stdin.readline
MAX_SIZE = 10**6+1
n = int(input())
arr = list(map(int,input().split()))

dic = {}
for i in range(n):
    tmp = arr[i]
    j = 2
    while tmp > 1:
        if tmp % j == 0:
            tmp = tmp // j
            if j in dic:
                dic[j] += 1
            else:
                dic[j] = 1
        else:
            j += 1

max_value = 1
res = 0
for k,v in dic.items():
    pow = v // n
    if pow == 0:
        continue
    max_value *= k**pow
    for num in arr:
        cnt = 0
        for i in range(pow):
            if num % k != 0:
                break
            num //= k
            cnt += 1
        res += (pow - cnt)
print(max_value,res)

---

시간복잡도

• 단순 나눗셈을 통한 소인수분해의 시간복잡도는 $O(\sqrt{N})$ 이다.
• 수가 $10^6$까지 일 때 dic에 모든 소수가 담길경우 약 $8*10^4$개라고 가정할 수 있다.
• 따라서 $8*10^4 * N$ 정도의 시간을 예상할 수 있다.
• 최대 상수로 시간복잡도를 계산해 보면 약 $O(8*10^6)$의 시간복잡도가 소요된다.