14.6_마법의 약_POTION

문제 설명

algospot.com :: POTION

• n종류의 재료를 각각 r숟가락씩 넣어서 마법의 약을 만든다.(1 <= n <= 200, 1 <= r <= 1000)
• 이미 각 p만큼의 재료가 들어있다.(0 <= p <= 1000)
• 모든 재료를 정확히 넣으면 정확히 한 병 분량이 된다.
• 약의 비율을 정확히 맞춰야 하며 최소 한 병 이상의 약을 만들어야 한다.
• 항상 한 숟가락 단위로 재료를 넣는다.

=> 넣어야 할 각 재료의 최소량을 출력하기

 

문제 풀이

재료의 비율 구하기

이 문제는 약의 비율을 유지해야 한다는 조건이 있다.

그러므로 넣어야 할 약의 비율을 우선 구해야 한다.

 

비율 a:b에서 a와 b는 1을 최대공약수로 하는 숫자들이다.

2 : 4 는 2를 최대공약수로 가지기 때문에 비율을 구하면 1 : 2가 된다.

 

따라서 재료 r의 비율을 구하려면 모든 r을 최대공약수로 나누어야 한다.

r들의 최대공약수를 구한 후, 그것으로 나누어 _r 배열을 만들어주었다.

 

몇 숟가락을 더 넣어야 할까

재료 r의 비율에 맞춰 현재 들어간 재료 p 에서 몇 숟가락씩을 더 넣어야 할까?

재료의 비율을 유지하며 약을 넣으려면 각 비율에 해당하는 수만큼씩을 더 넣어주면 된다.

따라서 1, 2, ...,  x배만큼 재료를 더 넣어보자.

 

모든 r을 x배 한 숫자가 모든 p보다 클 때, 현재 들어간 재료에 추가로 재료를 넣으며, 비율을 유지하면서 약을 만들 수 있다.

따라서 x값을 구한 후, p - r * x한 값이 추가로 넣어야 하는 재료 최소량이다.

 

문제 풀이 코드

#include <iostream>

using namespace std;

int n;
int r[201];
int _r[201];
int p[201];

int gcd(int a, int b) {
	if (b == 0)
		return a;
	return gcd(b, a%b);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int c;
	cin >> c;
	for (int tc = 1; tc <= c; ++tc) {
		cin >> n;
		for (int i = 0; i < n; ++i) {
			cin >> r[i];
		}
		for (int i = 0; i < n; ++i) {
			cin >> p[i];
		}
		
		// r의 최대공약수 구하기
		int gcdValue = r[0];
		for (int i = 1; i < n; ++i) {
			gcdValue = gcd(gcdValue, r[i]);
		}

		// 최대공약수로 나누기
		for (int i = 0; i < n; ++i) {
			_r[i] = r[i] / gcdValue;
		}

		// 최소 배수 구하기
		int mul = 1;
		for (; mul <= 1000; ++mul) {
			bool flag = true;
			for (int i = 0; i < n; ++i) {
				int val = _r[i] * mul;
                		// _r*mul이 p보다 커야하며(이미 들어간 재료양보다 많아야함), 
              			// r보다 커야함(1병이 되려면)
				if ((val < p[i]) || (val < r[i])) {
					flag = false;
					break;
				}
			}
			if (flag)
				break;
		}
		for (int i = 0; i < n; ++i) {
			cout << (_r[i] * mul - p[i]) << " ";
		}
		cout << endl;
	}
	return 0;
}