algospot 마법의 약 (문제 ID: POTION) c++

알고스팟 링크: https://algospot.com/judge/problem/read/POTION

algospot.com :: POTION

마법약 한개를 만드는데 필요한 재료들의 양이 주어질때, 재료들의 비율들을 맞춰서 1개이상의 마법약을 만드는데 필요한 각 재료들의 최솟값을 구하는 문제이다.

먼저 put/recipe가 최대인 값을 X라 할때, X이상의 마법약을 만들어야 한다.

하지만 해당 재료 뿐 아니라 다른 재료들의 양도 정수로 맞춰야 하므로 X이상이고 recipe들과의 곱이 항상 정수인 유리수 a/b(b는 recipe들의 최대공약수)만큼의 마법약을 만들면 된다.

 

	#include<iostream>
	#include<vector>
	using namespace std;
	// 각각 재료에 들어가야 하는 재료의 양, 이미 넣은 양, 앞으로 넣어야 되는 양
	vector<int> recipe, put, ret;
	int n;
	// a,b의 최소공배수 구하기 (gcd(p,q) == gcd(p-q, q)를 이용)
	int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
	}
	// a/b보다 작지않은 최소 자연수
	int ceil(int a, int b) {
	return (a + b - 1) / b;
	}
	// 재료들 중에서 put/recipe의 최댓값이 X라 할때
	// X이상이고 recipe들과의 곱이 항상 정수인 유리수를 a/b라고 하면 b는 recipe들의 최대공약수
	vector<int> solve() {
	int b = recipe[0];
	for (int i = 1; i < n; i++)
	b = gcd(b, recipe[i]);
	// 비율이 1은 넘어가야 하므로 a는 b이상이다.
	int a = b;
	for (int i = 0; i < n; i++)
	a = max(a, ceil(put[i] * b, recipe[i]));
	ret.resize(n);
	for (int i = 0; i < n; i++)
	ret[i] = recipe[i] * a / b - put[i];
	return ret;
	}
	int main() {
	int testcase;
	cin >> testcase;
	while (testcase--) {
	recipe.clear(); put.clear(); ret.clear();
	int r, p;
	cin >> n;
	for (int i = 0; i < n; i++) {
	cin >> r;
	recipe.push_back(r);
	}
	for (int i = 0; i < n; i++) {
	cin >> p;
	put.push_back(p);
	}
	solve();
	for (int i = 0; i < n; i++)
	cout << ret[i] << " ";
	cout << endl;
	}
	}

view raw algospot 마법의 약 (문제 ID: POTION).cpp hosted with ❤ by GitHub

코드원본: https://github.com/sbl133/JongmanBook/blob/main/14.%20NumberTheory/POTION.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1