[알고스팟] 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이 더 넣어야할 재료의 양이다.

 

 

코드