문제 링크
https://www.acmicpc.net/problem/2030
◆문제 해설 및 설명◆
문제 : 정수의 곱셈과 나눗셈으로만 이뤄진 임의의 수식을 받아, 그 결과가 정수이면 “민트 초코”를, 정수가 아닌 유리수이면 “치약”을 출력하여라.
처음 든 생각은 나누기 연산을 소숫점 버림을 해야 하는지, 현실처럼 분수로 작성해야하는 지였다.
예제 2를 보니 현실처럼 분수로 작성해함을 알 수 있었다. ( 소숫점 버림시, 2 / 3 = 0, 이후 0이므로 정답은 mint chocolate)
이를 일단 무식하게 *끼리 /끼리 연산후 마지막에 연산해주었더니, 아니나 다를까 런타임 에러 (IntegerOverflow)가 나왔다.
따라서 오버플로우가 나지 않게 만들어주기 위해 분자와 분모를 처리를 해주어야 하는데, 분모의 값을 분자에서도 나눠줘야 하기 때문에 일단 소인수분해를 통해 같은 배수를 제거 하도록 하였다.
수인수분해를 하기 위해서는 일단 소수를 알아야 했는데 이는 에라토스테네스의 체를 이용하였다.
(정수론에서 자주 나오는 개념이니 암기하자.)
에라토스테네스의 체를 통해서 N까지의 수 중에 가장 작은 소수부터 sqrt(N)까지 계속 나누게되면, 낮은 소수의 배수(소수가 아닌 수)로는 나눌 수 없기 때문에 쉽게 소인수 분해를 할 수 있다. (코드 설명은 아래에 따로 있다.)
void Factorization(int buf, bool divide)
{
int limit = sqrt(buf);
int d = divide ? -1 : 1;
for (int i = 2; i <= limit; i++)
{
while (!(buf % i))
{
buf /= i;
visit[i] += d;
}
}
if (buf > 1)
{
visit[buf] += d;
}
}while문을 통해서 소수의 배수인지 확인하고, 맞다면 값을 해당 소수로 나눠주고 visit[i]에 곱하기면 +1 나누기면 -1을 하였다.
visit[i]의 의미는 i값이 양수면 분자에 visit[i]만큼 있고, i값이 음수면 분모에 visit[i]만큼 있음을 나타낸다.
그리고 아래에 if절로 buf > 1인지 확인을 하는데, 이유는 에라토스테스의체의 경우 배수 검색을 sqrt(N)까지만 하기 때문에, N이 배수인지는 반복문에서 확인할 수 없지만, buf가 나눠지지 않았다는것은 소수임을 나타냄으로 작성되었다.
진행과정은 아래와 같다. (예제 1번)
- * 1은 소수가 아니고 결과에 영향을 미치지 못함으로 초기값을 유지한다.
- * 2 는 소수 2로 이루어져있고 곱하기라서 때문에 visit[2]에 +1 해준다.
- / 3 은 소수 3로 이루어져있고 나누기라서 때문에 visit[3]에 -1 해준다.
- / 4 은 소수 2 * 2로 이루어져있고 나누기라서 때문에 visit[2]에 -2 해준다.
- * 5 는 소수 5로 이루어져있고 곱하기라서 때문에 visit[5]에 +1 해준다.
- 마지막으로, * 6 는 소수 3 * 2로 이루어져있고 곱하기라서 때문에 visit[2]와 visit[3]에 각각 +1 해준다.
●이때, 음수가 하나도 없음으로 분모가 없음(1)을 알 수 있고 따라서 답은 mint chocolate이다.
◆코드 전문◆
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int visit[100010];
bool mint = true;
void Factorization(int buf, bool divide)
{
int limit = sqrt(buf);
int d = divide ? -1 : 1;
for (int i = 2; i <= limit; i++)
{
while (!(buf % i))
{
buf /= i;
visit[i] += d;
}
}
if (buf > 1)
{
visit[buf] += d;
}
}
int main()
{
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
int N, answer, maxI;
cin >> N;
cin.get();
cin >> answer;
answer = abs(answer);
maxI = abs(answer);
vector<int> buf(N);
buf[0] = answer;
vector<char> oper(N);
oper[0] = '*';
for (int i = 1; i < N; i++)
{
cin.get();
cin.get(oper[i]);
cin.get();
cin >> buf[i];
buf[i] = abs(buf[i]);
maxI = max(maxI, buf[i]);
}
for (int i = 0; i < buf.size(); i++)
{
if (oper[i] == '*')
{
Factorization(buf[i], false);
if (buf[i] == 0)
{
cout << "mint chocolate";
return 0;
}
}
else
{
Factorization(buf[i], true);
}
}
for (int i = 0; i <= maxI; i++)
{
// cout << visit[i] << " ";
if (visit[i] < 0)
{
mint = false;
break;
}
}
if (mint)
{
cout << "mint chocolate";
}
else
{
cout << "toothpaste";
}
return 0;
}음수는 유리수인지는 상관이 없기 때문에 abs()를 통해 양수로 바꾸어 주었다.
buf배열과 oper배열에 숫자와 연산자를 저장하고, 숫자의 최댓값을 visit[i]의 순회 검사를 위해 저장해 주었다.
이후 oper배열에 값에 따라 Factorization함수의 매개변수를 달리하여 호출하였다.
Factorization의 첫번 쨰 매개변수는 숫자 값, 두번째 매개변수는 /연산자를 사용하였는지에 대한 bool 값이다.
void Factorization(int buf, bool divide)
limit변수를 선언하여 에라토스네테스의 체의 최대값을 저장하였고, 3항 조건문 연산자를 통해 /이면 빼기를 *이면 더하기를 해주었다.
반복문을 통해 소인수 분해를 해주었고, 그 소수에 해당하는 값을 visit[i]에 연산해주었다.
에라토스네테스의 체의 최대값에 도달하여 모든 소수의 배수를 검사했다면 if절을 통해 자신이 소수인지 판별하고 맞다면 이를 연산해주었다.
void Factorization(int buf, bool divide)
{
int limit = sqrt(buf);
int d = divide ? -1 : 1;
for (int i = 2; i <= limit; i++)
{
while (!(buf % i))
{
buf /= i;
visit[i] += d;
}
}
if (buf > 1)
{
visit[buf] += d;
}
}
이후 연산이 종료되고, visit[]에서 음수를 발견한다면 분모가 1이 아님으로 바로 출력문을 결정하는 mint(정수)를 false로 만들고 아니라면, true인채로 반복문이 종료 되고
mint의 값에 따라 출력문을 결정한다.
for (int i = 0; i <= maxI; i++)
{
// cout << visit[i] << " ";
if (visit[i] < 0)
{
mint = false;
break;
}
}
if (mint)
{
cout << "mint chocolate";
}
else
{
cout << "toothpaste";
}
return 0;
느낀점
에라토스테네스의 체를 소인수분해에도 이렇게 효율적으로 사용할 수 있구나라는것을 알 수 있었다.
처음에는 받은 최대값 까지의 소수를 구하고 연산을 하였는데, 시간초과가 나왔다.
그래서 작은 소수부터 나눠진다면 나눠서 저장하는 방법을 사용하였는데, 수학의 신비로움을 알 수 있었다.
또한 배열을 통해 분모와 분자를 나타낸다는 발상이 정말 신기하였다.
