백준 20302 - 민트 초코

문제 설명

상원이는 아주 특별한 방법으로 디저트를 고른다.

상원이는 정수의 곱셈과 나눗셈으로만 이뤄진 임의의 수식을 적고, 그 결과가 정수이면 “민트 초코”를, 정수가 아닌 유리수이면 “치약”을 먹기로 했다.

상원이가 적은 수식이 주어졌을 때, 어떤 디저트를 먹게 될지 맞혀보자.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 수식의 결과가 정수라면 민트 초코 그렇지 않으면 치약을 출력하면 된다.

 

수식은 *, /로만 이루어져 있다.

따라서, * 뒤에 나오는 수는 분자로 / 뒤에 나오는 수는 분모로 적용된다고 생각할 수 있다.

모든 분자와 분모를 소인수 분해하여 나타낸다면 상쇄되는 수가 존재한다.

모든 상쇄되는 수를 제거하고 남은 수들을 보았을 때 분모에 수가 남아있다면 이는 정수가 될 수 없다.

 

이를 표현하기 위해 배열을 하나 사용하여 소인수 분해한 수들을 카운팅 할 수 있다.

분자에 나오는 수는 +를 분모에 나오는 수는 -를 적용하여 계산하면 된다.

 

소인수 분해는 다음과 같이 진행하면 된다.

void Check(int n, bool bChild)
{
	//소인수 분해
	for (int i = 2; i * i <= n; i++)
	{
		while (n % i == 0)
		{
			child[i] += bChild ? 1 : -1;
			n /= i;
		}
	}

	if (n > 1)
	{
		child[n] += bChild ? 1 : -1;
	}
}

 

한 가지 주의할 점은 0이 주어지는 경우이다.

문제의 규칙에 의해 0으로 나누어지는 경우는 주어지지 않는다.

따라서, 0이 주어진다면 이는 무조건 곱해지는 수이다.

어떠한 수에 0을 곱하게 되면 그 수는 무조건 0이 된다.

따라서 0이 나오는 순간 정수가 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;

int N, n;
int MAX = 100'000;
vector<int> child(MAX, 0);

void Check(int n, bool bChild)
{
	//소인수 분해
	for (int i = 2; i * i <= n; i++)
	{
		while (n % i == 0)
		{
			child[i] += bChild ? 1 : -1;
			n /= i;
		}
	}

	if (n > 1)
	{
		child[n] += bChild ? 1 : -1;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	int inputCnt = 2 * n - 1;
	bool flag = true;
	string s;

	for (int i = 0; i < inputCnt; i++) 
	{
		cin >> s;
		if (i % 2 == 1) 
		{
			if (s == "*") flag = true;
			else flag = false;
			continue;
		}

		if (s == "0")
		{
			cout << "mint chocolate";
			return 0;
		}

		Check(abs(stoi(s)), flag);
	}

	
	for (int i = 2; i <= MAX; i++) 
	{
		if (child[i] < 0) 
		{
			cout << "toothpaste";
			return 0;
		}
	}

	cout << "mint chocolate";
	return 0;
}

---