[Python] 20302번 민트 초코

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

20302번: 민트 초코

---

 

24/02/13

 

 

자잘한 실수를 많이 해 애를 많이 먹었던 문제입니다.

 

제가 잘못 접근했던 순으로 문제를 설명하고자 합니다.

---

 

문제 접근 방식:

 

 

문제에서 주어지는 정보는 간단합니다.

 

주어진 수식을 순서대로 계산하고, 그 결과가 정수인지 유리수인지 판별하는 것입니다.

 

파이썬을 사용하고 있다면 가장 흔하게 저지를 수 있는 실수는, 너무 간단한 풀이를 떠올려 구현하는 것입니다.

 

 

1. 파이썬에는 eval()이라는 함수가 존재해서, 주어진 수식의 값을 계산해줍니다.

 

이를 사용하면 쉽게 구현할 수 있을 것이라고 생각할 수 있지만, 문제에서 주어진 수의 범위가 최대 $100,000$이고, 이 수가 최대 $100,000$개 주어지므로, 나눗셈을 많이 하게 되면 정밀도가 떨어지게 됩니다.

 

또한, 수가 너무 커져 계산하는 데에 시간 초과를 받을 수 있기 때문에, 적절하지 않은 접근입니다.

 

2. 정밀도 문제를 해결하기 위해 Fractions 모듈을 사용하는 것 또한 적절하지 않습니다.

 

기본적으로 Fractions모듈은 매우 느립니다. 문제에서 주어진 수의 범위가 최대 10만임을 기억하고, 이 수가 최대 10만 번까지 주어짐을 생각해 보면, 계산하는 데에 시간이 다 지나갈 것입니다.

 

3. Fraction 모듈이 느리다는 점 때문에, math모듈의 gcd함수를 사용해 직접 나눠주어 기약 분수로 만드는 행위 또한 적절하지 않습니다.

 

Fraction모듈의 계산 속도를 개선할 수는 있겠지만, 곱하기만 잔뜩 주어져 있고, 큰 숫자를 10만 번 곱하는 행위 자체는 시간이 매우 오래 걸리기 때문에 기약 분수로 만드는 행위와는 관련이 없습니다.

 

즉, 2번 접근과 같은 이유로 시간 초과를 받습니다.

 

4. 곱하기를 할 때는 분자에 곱하고, 나누기를 할 때는 분모에 곱해서 따로따로 구현하는 것 또한 느립니다.

 

2번 접근과 같은 이유입니다.

 

 

즉, 결론적으로 그냥 나이브하게 곱해서 수식을 계산하는 아이디어는 모두 시간 초과를 받을 수밖에 없습니다.

 

그러면 어떻게 유리수인지를 판단할 수 있을까요?

 

위의 4번 접근의 아이디어를 발전시켜 보면, 결국 분모와 분자를 따로 보고, 서로 약분을 할 때, 분모에는 있는데 분자에는 없는 "소수"가 존재한다면 유리수라고 판단할 수 있을 것입니다.

 

즉, 입력이 들어올 때마다 소인수 분해를 진행하여, 지금까지 수식을 계산했던 모든 소인수들의 개수를 저장하면 될 것입니다.

 

곱셈을 진행할 때에는 소인수의 개수를 더해주면 되고, 나눗셈을 진행할 때에는 소인수의 개수를 빼주면 됩니다.

 

최종 결과에, 소인수의 개수 중에서 "음수"가 존재한다면, 이는 분모에는 있는데 분자에는 없는 소인수라는 뜻이므로 유리수로 판단할 수 있습니다.

 

가장 유의해야 할 점은, $0$의 예외처리입니다.

 

$0$으로 나누는 수식은 주어지지 않지만 $0$으로 곱하는 수식이 주어짐에 유의합시다.

 

$0$이 곱해지는 수식은 어떠한 경우든 항상 정수입니다.

 

$1$을 곱하거나 나눌 때에 예외처리를 함에 유의합시다. $1$은 소수도, 합성수도 아니기 때문에 아무것도 하지 않아도 됩니다.

 

$-1$도 마찬가지입니다.

 

또한, 소인수분해를 진행할 때 빠른 소인수 분해를 해야 함에 유의합시다.

 

소인수분해 코드가 너무 나이브하면 시간 초과를 받을 수 있습니다.

 

이러한 점들을 모두 고려하여, 문제를 해결할 수 있습니다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 20302번 민트 초코
# 구현, 수학, 에라토스테네스의 체
import sys
input = sys.stdin.readline

# 100_000보다 작은 소수 중 가장 큰 소수는 999_91
primes = [0 for _ in range(999_92)]
sieve = [1 for _ in range(100_001)]
sieve[0], sieve[1] = 0, 0
for i in range(2, 318): # sqrt(100_000) = 316
    if sieve[i]:
        for j in range(i*i, 100_001, i):
            sieve[j] = 0

# n이 2이상일 때 작동하는 함수
def factorize(n):
    dic = dict()
    if sieve[n]:
        dic[n] = 1
        return dic
    prime = 2
    while prime*prime <= n:
        if n % prime == 0:
            dic[prime] = 0
            while n % prime == 0:
                dic[prime] += 1
                n //= prime
        prime += 1
    if n in dic:
        dic[n] += 1
    if sieve[n]:
        dic[n] = 1
    return dic

def mul(n):
    if n == 1: return
    for prime, times in factorize(n).items():
        primes[prime] += times

def div(n):
    if n == 1: return
    for prime, times in factorize(n).items():
        primes[prime] -= times

N = int(input())
I = input().split()
start_num = abs(int(I[0]))
if start_num == 0:
    print('mint chocolate')
    exit()
mul(start_num)
for i in range(N-1):
    command, num = I[2*i+1], abs(int(I[2*i+2]))
    if num == 0:
        print('mint chocolate')
        exit()
    if command == '*':
        mul(num)
    else:
        div(num)

for i in range(999_92):
    if primes[i] < 0:
        print('toothpaste')
        exit()
print('mint chocolate')