[algospot] POTION

문제링크 입니다

🚀 [POTION] 문제 😊😊😊😊😊

마법의 약 수업 시간에 교수님의 설명을 안 듣고 졸던 헤리는 실수로 냄비에 몇 가지 재료의 양을 잘못 넣고 말았습니다. 약의 색깔이 심상치 않게 변하는 것을 눈치챈 해르미온느가 재빨리 레시피의 정확한 양을 알려주어서 약을 전부 망치는 것은 면했습니다. 지금 얼른 재료를 더 넣어서 약을 완성해야 합니다.

이번 시간에 만드는 마법의 약은 n 종류의 재료를 각 ri 숟가락씩 넣어서 만들어야 합니다. 모든 재료를 정확히 넣었을 경우 만들어진 마법의 약은 정확히 한 병 분량이 됩니다. 헤리가 이미 냄비에 넣은 각 재료들의 양은 pi 로 주어집니다. 헤리는 적절히 냄비에 재료를 최소한으로 더 넣어 각 재료의 비율을 정확히 맞추고 싶습니다. 이를 위해 한 병보다 많은 약을 만들어도 상관 없지만, 최소한 한 병은 만들어야 합니다. 헤리는 항상 숟가락 단위로만 재료를 넣을 수 있기 때문에, 반 숟가락의 재료를 더 넣는다거나 하는 일은 불가능합니다.

넣어야 할 각 재료의 최소량을 계산하는 프로그램을 작성하세요.

🔑 [풀이]

먼저 레시피의 비율을 알기위해 최대 공약수를 구한다.
현재 들어가 있는 재료와 레시피의 간의 비율이 최대인 배수를 구해 a 에 저장한다. ex 4 6 2 4 -> gcd로 나누면 2 3 1 2 -> 넣어져있는 재료 6 4 2 4 -> 6 / 2 가 최대로 3이다.
이후 a를 기준으로 레시피 비율 * a 에서 넣어져 있는 재료의 양을 빼주면 -> 추가로 넣어야 할 재료의 양을 구할 수 있다.\

⌨️ 입력

입력의 첫 줄에는 테스트 케이스의 수 c (c <= 50) 가 주어집니다. 각 테스트 케이스는 세 줄로 구성됩니다. 첫 줄에는 재료의 수 n (1 <= n <= 200) 이 주어지고, 다음 줄에는 n 개의 정수로 약에 들어가야 하는 각 재료의 양 ri (1 <= ri <= 1000), 그 다음 줄에는 n 개의 정수로 이미 냄비에 넣은 재료의 양 pi (0 <= pi <= 1000) 가 주어집니다.

🖥 출력

각 테스트 케이스마다 한 줄에 n 개의 정수로 각 재료마다 더 넣어야 하는 양을 출력합니다.

🖱 입력 예제

3
4
4 6 2 4
6 4 2 4
4
4 6 2 4
7 4 2 4
3
4 5 6
1 2 3

💻 출력 예제

0 5 1 2
1 8 2 4
3 3 3

💎 전체 코드는 다음과 같습니다.

//
//  POTION.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/11/13.
//

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("POTION.txt");

int n;
/*
 recipe 의 최대 공약수를 구해라.
 */
int gcd(int p, int q){
    return q==0 ? p : gcd(q,p%q);
}
int ceil(int a, int b){
    return (a + b - 1) / b;
}
vector<int> solve(const vector<int> &recipe, const vector<int> &puts){
    // 최대 공약수를 구한다.
    int b = recipe[0];
    for(int i=1; i<n; i++){
        b = gcd(b, recipe[i]);
    }
    // a = 레시피에 비해 가장 많이 들어있는 재료비율 -> 기준
    int a = b;
    for(int i=0; i<n; i++){
        a = max(a, ceil(b*puts[i],recipe[i]));
    }
    vector<int> ret(n);
    // 더 넣어야할 양을 ret 컨테이너에 추가.
    for(int i=0; i<n; i++){
        ret[i] = a*(recipe[i]/b) - puts[i];
    }
    return ret;
}
int main(){
    int test_case;
    fin >> test_case;
    for(int test=0; test < test_case; test++){
        fin >> n;
        vector<int> recipe(n);
        vector<int> puts(n);
        int temp=0;
        for(int i=0; i<n; i++){
            fin >> recipe[i];
        }
        for(int i=0; i<n; i++){
            fin >> puts[i];
        }
        vector<int> result = solve(recipe, puts);
        for(int i=0; i<result.size(); i++){
            cout << result[i] << " ";
        }
        cout << endl;
        recipe.clear();
        puts.clear();
    }
}