20302번: 민트 초코
상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다.
www.acmicpc.net
아이디어:
문제에 어떻게 접근해야하는지 도무지 모르겠다. 단순하게 풀면 풀리지 않을 거라는 건 자명하고, 소인수분해를 이용하여 풀어야 하는 것 같은데 정수와 정수가 아닌 유리수를 소인수분해를 이용해서 어떻게 알 수 있을까?
분모와 분자를 각각 소인수분해해서 나눴을때 분모에 소수가 남으면 정수가 아니다..
곱셈 뒤에 있는 수는 분자, 나눗셈 뒤는 분모..
각 수를 소인수분해하고 분자인 경우에는 해당하는 소수를 +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")
'알고리즘💻 > map&set&number theory' 카테고리의 다른 글
BOJ 16563번: 어려운 소인수분해 (0) | 2021.02.19 |
---|---|
BOJ 14490번: 백대열 (0) | 2021.02.19 |
BOJ 2002번: 추월 (0) | 2021.02.19 |
BOJ 4358번: 생태학 (0) | 2021.02.19 |
20302번: 민트 초코
상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다.
www.acmicpc.net
아이디어:
문제에 어떻게 접근해야하는지 도무지 모르겠다. 단순하게 풀면 풀리지 않을 거라는 건 자명하고, 소인수분해를 이용하여 풀어야 하는 것 같은데 정수와 정수가 아닌 유리수를 소인수분해를 이용해서 어떻게 알 수 있을까?
분모와 분자를 각각 소인수분해해서 나눴을때 분모에 소수가 남으면 정수가 아니다..
곱셈 뒤에 있는 수는 분자, 나눗셈 뒤는 분모..
각 수를 소인수분해하고 분자인 경우에는 해당하는 소수를 +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")
'알고리즘💻 > map&set&number theory' 카테고리의 다른 글
BOJ 16563번: 어려운 소인수분해 (0) | 2021.02.19 |
---|---|
BOJ 14490번: 백대열 (0) | 2021.02.19 |
BOJ 2002번: 추월 (0) | 2021.02.19 |
BOJ 4358번: 생태학 (0) | 2021.02.19 |