[알고스팟] POTION - 마법의 약 (C++, 유클리드 최대공약수)

문제

https://algospot.com/judge/problem/read/POTION

algospot.com :: POTION

 

 

풀이

 

유클리드의 최대공약수 알고리즘을 활용하는 문제이다. 

 

해당 문제에서 다른 건 몰라도 한 가지 확실한 것은 (이미 넣은 재료양)/(레시피 재료 양)의 비가 최대인 것보다 크거나 같은 크기의 약을 만들어야 한다는 것이다.

 

이러한 비를 already_put / recipe (최대비)라고 나타내 보자.

이보다 크거나 같은 비는 k/b(넣을 약의 비)라고 나타내면 아래와 같다.

 

already_put / recipe  <=  k/b 

최대 비 <= 넣을 약의 비

 

그런데 항상 숟가락 단위(정수 단위)로만 재료를 넣을 수 있기 때문에 recipe들과 넣을 약의 비(k/b)는 항상 정수여야만 한다.

(recipe*k)/b == 정수

 

따라서 recipe들은 b로 나누어 떨어져야 한다.

즉, 모든 recipe들의 최대 공약수가 해당 조건을 만족시킨다.

(아래에서부터 b는 gcd로 표기)

 

아래는 재귀함수가 아닌 while문으로 구현한 recipe들의 최대공약수(gcd)를 구하는 함수이다.

이해가 잘 되지 않는다면, 최대 공약수를 구하는 알고리즘인 유클리드 알고리즘을 공부하고 오자.

//링크 추가 중..

 

int RecipeGcd(){
  int a,b;
 
  if(material_num ==1)
    return recipe[0];
 
  a = recipe[0];
  for(int i=1; i<material_num ; ++i){
    b = recipe[i];
    while(b!=0){
      a %= b;
      swap(a,b);
    }
  }
  return a;
}

 

레시피들의 gcd를 구했다면

already_put / recipe  <=  k/gcd

(already_put * gcd)/ recipe  <=  k

이제 최대 비*gcd보다 크거나 같은 가장 작은 k의 값을 구해보자.(단, 약은 한 개 이상 만들어야 하므로 k는 gcd와 같거나 큰 값이다.)

 

아래의 ceil함수로 a/b보다 크거나 같은 최소 자연수를 간단히 구할 수 있다.

 

int ceil(int a, int b){
  return (a+ b -1)/b;
}

 

+만약 a가 0가 0이라면 (b-1)/b는 0이기 때문에 해당 함수는 항상  a/b보다 크거나 같은 최소 자연수를 반환한다.

 

이제 k와 gcd의 값을 모두 구했으므로 추가적으로 넣어야 할 재료를 계산하자.

 

recipe * 만들 물약의 비 (k/gcd)가 k/gcd 개의 물약을 만드는데 필요한 재료의 양이다.

따라서 (recipe*k)/gcd - already_put이 더 넣어야할 재료의 양이다.

 

 

코드

	#include <iostream>
	#include<vector>
	using namespace std;
	int material_num;
	int recipe[200];
	int already_put[200];
	int RecipeGcd(){
	int a,b;
	if(material_num ==1)
	return recipe[0];
	a = recipe[0];
	for(int i=1; i<material_num ; ++i){
	b = recipe[i];
	while(b!=0){
	a %= b;
	swap(a,b);
	}
	}
	return a;
	}
	int ceil(int a, int b){
	return (a+ b -1)/b;
	}
	int main() {
	ios_base::sync_with_stdio(0);
	int test_num,temp,gcd;
	cin>>test_num;
	while(test_num--){
	cin>>material_num;
	for(int i=0; i<material_num ; ++i)
	cin>>recipe[i];
	for(int i=0; i<material_num ; ++i)
	cin>>already_put[i];
	gcd = RecipeGcd();
	int k = gcd;
	for(int i=0; i<material_num ; ++i)
	k = max(k, ceil(already_put[i]*gcd, recipe[i]));
	for(int i=0; i<material_num ; ++i)
	cout<< (recipe[i]*k)/gcd - already_put[i]<<' ';
	cout<<'\n';
	}
	return 0;
	}

view raw [AlgoSpot]_POTION_마법의 약.cpp hosted with ❤ by GitHub