칵테일 C++ - 백준 1033

https://www.acmicpc.net/problem/1033

문제 접근

재료 a와 재료 b가 p와 q비율을 가지려면

(편의상 a의 질량을 a, b의 질량을 b로 칭함)

$a\cdot q=b\cdot p$ 그리고 $a/p=b/q$ 이다.

문제 조건 중 하나인

"필요한 재료의 질량을 모두 더한 값이 최소가 되어야 한다."

가 있기 때문에 $a/p$와 $b/q$는 최소여야 할 것이다.

또한 재료의 질량은 자연수이기 때문에 처음 시작은

모두 인자 $1$을 가지면서 시작한다.

비율 $p,q$에 대하여 인자가 1인 상태에서는 $p,q$를 곱해주면 끝난다.

하지만 다른 재료에 의해서 다른 수가 곱해져있어

$a/p!=b/q$를 만족하는 상황이 생긴다.

3
0 1 9 8
1 2 9 8

4
2 3 6 8
0 1 9 3
3 0 7 5

이 상황에서는 $a/p==b/q$를 만족시키면서 진행해야 하기 때문에

$a/p$와 $b/q$를 제일 작으면서 인수가 같은 수로 만들어야 한다.

그 수는 자명히 $gcd(a,b)\cdot a\cdot b$이다.

아직 $p,q$를 곱하지 않았으므로

$p/gcd(p,q)$와 $q/gcd(p,q)$를 곱해준다.

그런데 $p/gcd(p,q)$와$ $q/gcd(p,q)$를 곱하지 않아도

비율이 $p:q$이 만들어지는 상황이 있다.

$a=15,b=7,p=1,q=7$인 상황을 보자

이 경우에는 질량을 최소로 만드려면

$a,b$를 동일한 수로 두지 않고,

$a$는 놔두고 $b$만 $105$로 만들어주면 된다.

따라서 $a,b$에 각각 곱해지는 수의 $gcd$를 구해주면 된다.

이때 다른 재료들과도 비율을 지켜야 하므로 비율이 주어진

다른 재료들에도 똑같은 값을 곱해주면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

vector<int> num(10,1);
vector<int> con[10];

void dfs(vector<bool> &vis,int cur, int mul){
    for(int i=0;i<con[cur].size();i++){
        int node=con[cur][i];
        if(!vis[node]){
            num[node]*=mul;
            vis[node]=1;
            dfs(vis,node,mul);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n;
    cin >> n;
    for(int i=1;i<n;i++){
        vector<bool> vis(10,0);
        int a,b,p,q;
        cin >> a >> b >> p >> q;
        int mula=num[b]/gcd(num[a],num[b])*p/gcd(p,q);
        int mulb=num[a]/gcd(num[a],num[b])*q/gcd(p,q);
        int imgcd=gcd(mula,mulb);
        mula/=imgcd;
        mulb/=imgcd;
        vis[a]=1; vis[b]=1;
        dfs(vis,a,mula);
        dfs(vis,b,mulb);
        num[a]*=mula;
        num[b]*=mulb;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    for(int i=0;i<n;i++) cout << num[i] << ' ';
    return 0;
}