[정수론] POTION 마법의 약

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
 
using namespace std;
 
int T, n;
int r[200]; 
int p[200];
vector<double> ratio;
int add[200];
 
void potion()
{
    if(ratio.back() <= 1.0)
    {
        for(int i = 0; i < n; i++)
            cout<<r[i] - p[i]<<" ";
        cout<<"\n";
    }
    else 
    {
        double maxr = ratio.back();
        int ratioN = ratio.back();
        for(int i = 0; i < n; i++)
            if(ratioN * r[i] - p[i]> 0)
                add[i] = ratioN * r[i] - p[i];
        for(int i = 0; i < n; i++)
        {
            double pr = (double)(p[i]+add[i])/r[i];
            while(ratio.back() > pr)
            {
                add[i]++;
                pr = (double)(add[i]+p[i])/r[i];
            }
            if(maxr < pr) maxr = pr;
        }
        if(maxr > ratio.back())
        {
            for(int i = 0; i < n; i++)
                if(((int)ceil(maxr) * r[i] - (p[i] + add[i])) > 0)
                    add[i] += ((int)ceil(maxr) * r[i] - (p[i] + add[i]));
        }
        for(int i = 0; i < n; i++)
            cout<<add[i]<<" ";
        cout<<"\n";
    }
}
 
int main()
{
    cin>>T;
    for (int i = 0; i < T; i++)
    {
        ratio.clear();
        memset(add, 0, sizeof add);
        cin>>n;
        for(int j = 0; j < n; j++)
            cin>>r[j];
        for(int j = 0; j < n; j++)
            cin>>p[j];
        ratio.resize(n);
        for(int j = 0; j < n; j++)
            ratio[j] = (double)p[j]/r[j];
        sort(ratio.begin(), ratio.end());
        potion();
    }
}

1. 풀이

모든 재료의 비율을 똑같이 맞추는 문제이다.

따라서 만약 가장 큰 비율보다 작을 경우 비율을 맞추기 위해

하나씩 추가하여 비율을 맞추었다.

 

또한 위 코드에서는 한번 처리 후 비율이 맞지 않을경우

가장 큰 비율을 올림하여 레시피의 정수배만큼 제조하였다

 

2. 책의 풀이1

 

i번 재료가 put[i]/recipe[i] 배 들어갔으니 

j번 재료도 최소한 그만큼 넣어야한다는 것을 식으로 풀었다.

 

put[j] >= recipe[j] * put[i] / recipe[i]

 

이식을 통해 냄비에 재료를 더 넣지 않아도 될 때까지 

이중 포문으로 i와 j를 비교하였다.

 

3. 책의 풀이2

모든 재료중 가장 많이 들어간 재료를 찾는다.

 

X = max (put[i]/recipe[i])

 

모든 재료는 X배 이상 들어가야한다는 사실을 알 수 있다.

 

하지만 recipe[i]*X는 항상 정수여야한다.

 

따라서 실제 곱해야하는 유리수는 다음과 같다

 

X <= Y = a/b

 

이제 Y를 찾으면 된다.

 

모든 i에 대해 recipe[i]*Y 가 정수가 되기 위해서는 

b가 recipe[]의 모든 수들의 약수가 되어야한다.

즉. b는 recipe들의 최대 공약수여야 한다.

 

Xb <= a 를 만족하는 최소의 정수 a를 선택하면 문제를 풀 수 있다.

 

모든 레시피는 이제  1/b병으로 나눌 수 있게되었다.

그러므로 x이상이 될때 까지 1/b병을 계속 추가 시키면 답을 구할 수 있다.

 

또한 최대값 x를 구하고 거기에 b를 곱해서 a를 얻는게 아니라

|b*put[i]/recipe[i]|의 최대치를 직접 구함으로써 분수연산을 없앨 수 있다.

 

( ceil == (a+b-1)/b)

 

 

POTION