[백준 20302번] 민트 초코 (C++)

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

입력받는 모든 수를 소인수 분해 해서 곱셈과 나눗셈으로 나눠주면 된다.

곱셈일 때는 등장하는 소수의 개수만큼 배열에서 더해주고, 나눗셈일 때는 반대로 빼주면 된다.

최종 배열을 탐색하면서 0보다 작은 값이 있으면 분모에 해당 소인수가 살아있다는 뜻이므로 결과가 유리수가 된다.

소인수분해하는 코드를 알아가기 좋은 문제다.

 

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#define endl "\n"
using namespace std;

int n, num;
vector<int> arr(100001,0);

void fac(int a, bool check){
	int tmp = sqrt(a);
	if(check){
		for(int i = 2; i <= tmp; i++){
			while(a%i == 0) {
				arr[i]++;
				a /= i;
			}
		}
		if(a > 1) arr[a]++;
	}
	else {
		for(int i = 2; i <= tmp; i++){
			while(a%i == 0) {
				arr[i]--;
				a /= i;
			}
		}
		if(a > 1) arr[a]--;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin >> n;
	int inputCnt = 2*n-1;
	bool flag = true;
	bool zeroCheck = false;
	string s;
	for(int i = 1; i < inputCnt+1; i++){
		cin >> s;
		if(i%2 == 0){
			if(s == "*") flag = true;
			else flag = false;
			continue;
		}
		if(s == "0") zeroCheck = true;
		fac(abs(stoi(s)),flag);
	}
	if(zeroCheck) {
		cout << "mint chocolate";
		return 0;
	}
	for(int i = 2; i < 100001; i++){
		if(arr[i] < 0) {
			cout << "toothpaste";
			return 0;
		}
	}
	cout << "mint chocolate";
}