문제 링크 : https://www.algospot.com/judge/problem/read/POTION
(알고스팟)
문제 이해
어떤 약을 한 단위 만드는 데 필요한 n개의 재료들의 양과
현재 넣은 재료의 양이 입력된다.
이 때 약을 만들기 위해 더 넣어야 하는 재료들의 양을 구하는 문제이다.
입력값은 모두 정수이고,
약을 최소한 1단위 이상은 만들어야 한다.
풀이
완성한 약의 양이 꼭 정수단위일 필요가 없다는 점에 주의해야 한다.
따라서 필요한 재료들의 양을 최대공약수로 나누어
들어가야 하는 재료들의 비를 구했다.
예를 들어 들어가야 하는 3가지 재료의 양이 각각 2 4 6 이라면
최대공약수 2로 나누어 1 2 3 라는 비율을 구한다.
이제 들어가야 하는 재료의 양은 1 2 3 의 정수배인
1 2 3
2 4 6
3 6 8
4 8 10
...
...
과 같이 된다.
(정수배인 이유는 입력되는 재료의 양이 정수이므로)
그런데 문제에서 완성 약을 한 단위 이상 만들어야 한다는 조건이 있으므로
2 4 6 다음부터 검사하면 되는것이다.
여기서 현재 넣은 재료가 3 6 7 이라면
재료추가로 만들 수 있는 값이 위 정수배들 중에서 3 6 8 이므로
약을 완성시키기 위해 0 0 1 만큼의 재료를 더 넣어야 하는 것이다.
최대공약수를 구하는 부분은 유클리드 알고리즘을 사용하였고,
n개 수의 GCD를 구하기 위해 해당 알고리즘을 n-1번 반복하였다.
(관련글 : http://www.tibyte.kr/224)
코드
#include <cstdio>
#include <cmath>
using namespace std;
//GCD계산 (유클리드)
int calcGcd(int n1, int n2)
{
int temp;
if (n1 < n2) {
temp = n1;
n1 = n2;
n2 = temp;
}
while (n2 != 0) {
temp = n1%n2;
n1 = n2;
n2 = temp;
}
return n1;
}
int main(void)
{
int numTry;
scanf("%d",&numTry);
while (numTry--)
{
int numElem;
scanf("%d",&numElem);
int *ideal = new int[numElem];
int *curr = new int[numElem];
int gcd;
double curMul = 0;
double maxMul = 0;
int mul;
//비율값 입력받음
for (int i = 0; i < numElem; i++)
scanf("%d", &ideal[i]);
//비율값의 gcd계산
gcd = ideal[0];
for (int i = 1; i < numElem; i++)
gcd = calcGcd(gcd, ideal[i]);
//ideal값 재계산
for (int i = 0; i < numElem; i++)
ideal[i] = ideal[i]/gcd;
//현재넣은값 입력받음
for (int i = 0; i < numElem; i++) {
scanf("%d", &curr[i]);
curMul = (double)curr[i] / ideal[i];
if (curMul >maxMul ) maxMul = curMul;
}
mul = ceil(maxMul);
for (int i = 0; i < numElem; i++) {
ideal[i] *= mul;
printf("%d ", ideal[i] - curr[i]);
}
printf("\n");
}
return 0;
}