BOJ 20302번: 민트 초코

www.acmicpc.net/problem/20302

20302번: 민트 초코

아이디어:

문제에 어떻게 접근해야하는지 도무지 모르겠다. 단순하게 풀면 풀리지 않을 거라는 건 자명하고, 소인수분해를 이용하여 풀어야 하는 것 같은데 정수와 정수가 아닌 유리수를 소인수분해를 이용해서 어떻게 알 수 있을까?

분모와 분자를 각각 소인수분해해서 나눴을때 분모에 소수가 남으면 정수가 아니다..

 

곱셈 뒤에 있는 수는 분자, 나눗셈 뒤는 분모..

각 수를 소인수분해하고 분자인 경우에는 해당하는 소수를 +1로 카운트, 분모인 경우에는 -1로 카운트한다.

그리고 카운트 배열을 돌면서 음수가 있는지 확인하는데, 음수가 하나라도 있으면 정수가 아니므로 "toothpaste"를 출력하고 종료하고, 배열을 다 돈 후에도 음수가 없으면 정수이므로 "mint chocolate"를 출력한다.

 

그런데 이렇게 풀었더니 테스트 케이스는 모두 통과하는데 계속 8%에서 틀렸습니다. 가 떠서 머리 좀 쥐어뜯다가.. 문제를 다시 찬찬히 읽어보니 0으로 나누어지는 경우는 존재하지 않는다고 했지 곱하는 경우가 존재하지 않는다고는 안했다는 걸 알았다... 그래서 0을 곱하는 경우에는 바로 정수로판단하고 mint chocoalte를 출력 후 종료하는 조건을 추가했더니 통과되었다.

 

import sys

N = int(sys.stdin.readline())
exp = list(sys.stdin.readline().split())

matrix = [0]*(100000+1)
for i in range(1,100000+1):
    matrix[i]=i

for i in range(2, int(100000**0.5)+1):
    if (matrix[i]==i):
        for j in range(i*i, 100000+1, i):
            matrix[j]=i

cnt = [0]*(100000+1)
flag = 0
for i in exp:
    if (i=="*"):
        flag = 0
    elif (i=="/"):
        flag = 1
    else:
        n = int(i)
        if (n==0):
            print("mint chocolate")
            sys.exit(0)
        if (n<0): n*=-1
        if (flag==0):
            while(n>1):
                cnt[matrix[n]]+=1
                n//=matrix[n]
        else:
            while(n>1):
                cnt[matrix[n]]-=1
                n//=matrix[n]
for i in cnt:
    if (i<0):
        print("toothpaste")
        sys.exit(0)
print("mint chocolate")