[백준 20302] 민트 초코

문제

www.acmicpc.net/problem/20302

20302번: 민트 초코

 

풀이

1. 모든 합성수는 소인수분해를 통해 소수의 곱으로 표현할 수 있고, 그 개수들을 카운트하기 위해 소수들의 개수를 담는 배열을 사용합니다. 또한 정수, 유리수 판별에 음수 여부는 관계없으므로 편의를 위해 모두 양수로 바꿔줍니다.

 

2. 곱하는 수는 소인수 분해하여 표현된 소수들의 개수를 올려주고, 나누는 수는 소인수 분해하여 표현된 소수들의 개수를 빼주어 그 개수들을 관리할 수 있습니다. (곱하는 수 중 0이 존재한다면 항상 결과는 0이므로 이는 따로 처리해줍니다.)

 

3. 모든 수를 소인수분해하고나서 구간[2, 1e5] 소수 배열을 순회하는데 그 값이 음수인 경우 분모에 수가 남게 되는 것이므로 이는 유리수라고 판정할 수 있고, 그 외는 정수라고 출력하면 됩니다.

 

코드

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5;

int n, num, p[MAX + 1], sz;
char c;
bool zero, yuri;

void fac(int x) {
	sz = (int)sqrt(x);
	for (int i = 2; i <= sz; i++)
		while (!(x % i)) x /= i, p[i]++;
	if (x > 1) p[x]++;
}

void fac2(int x) {
	sz = (int)sqrt(x);
	for (int i = 2; i <= sz; i++)
		while (!(x % i)) x /= i, p[i]--;
	if (x > 1) p[x]--;
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	for (int i = 0; i < n; i++) {
		if (!i) {
			cin >> num;
			if (num < 0) num *= -1;
			else if (num == 0) zero = 1;
			if (num) fac(num);
		}
		else {
			cin >> c >> num;
			if (num < 0) num *= -1;
			else if (num == 0) zero = 1;
			if (c == '/') fac2(num);
			else if (num) fac(num);
		}
	}
	if (zero) cout << "mint chocolate";
	else {
		for (int i = 2; i <= MAX; i++)
			if (p[i] < 0) yuri = 1;
		if (yuri) cout << "toothpaste";
		else cout << "mint chocolate";
	}
}