[C++] 백준 칵테일

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

1033번: 칵테일

풀이

칵테일에 들어가는 N-1개 재료의 비가 주어질 때, 각 재료의 질량 총합이 최소가 되도록 하는 각각의 재료 질량을 구하는 문제입니다. 

 

따라서, 최대 공약수와 최소 공배수를 활용해서 문제를 해결할 수 있고, N개 중 N-1개의 값이 주어지므로 사이클 없는 그래프입니다.

 

a, b, p, q 형태로 값이 주어질 때,

1. a재료와 b 재료의 최대 공약수(gcd(p, q))로 나눈 재료비(ex. 9:6 -> 3:2)를 구합니다.
2. 각 재료의 현재 질량에 재료비를 곱해주면, 원하는 질량비를 만들기 위해 곱해줘야하는 수를 구할 수 있습니다. ex) a질량 4 b질량 3, 재료비 3:2를 맞춰야 할 때, 4x:3y = 3:2 가 성립하므로, 9y = 8x 입니다.  
3. 우리는 모든 질량 총합이 최소가 되어야 하므로, 재료비를 곱해준 재료 질량의 최대 공약수를 구하여 나눠준 값으로 업데이트 한다.
4. 업데이트 시, 연결된 모든 노드를 같이 업데이트 한다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

struct mat {
    int val = 1;
    vector<int> edge;
}arr[11];

bool visited[11];

int gcd(int a, int b)
{
    int tmp = 0;
    if (a < b) {
        tmp = a;
        a = b;
        b = tmp;
    }
    if (a % b == 0) return b;
    else 
        return gcd(b, a%b);
}

void update(int node, int mod) 
{
    arr[node].val *= mod; // 비율 반영
    visited[node] = true;
    for (auto e : arr[node].edge) {
        if (!visited[e]) {
            update(e, mod);
        }
    }
}

int main()
{ 
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    // freopen("test.txt", "r", stdin);
    int n, a, b, p, q, gcdVal, amod, bmod;
    cin >> n;
    for (int i=0; i < n-1; i++) {
        cin >> a >> b >> p >> q;

        gcdVal = gcd(p, q);
        amod = arr[b].val * p / gcdVal;
        bmod = arr[a].val * q / gcdVal;
        gcdVal = gcd(amod, bmod);

        memset(visited, 0, sizeof visited);
        update(a, amod/gcdVal);
        update(b, bmod/gcdVal);

        arr[a].edge.push_back(b);
        arr[b].edge.push_back(a);
    }

    for (int i=0; i<n; i++) 
        cout << arr[i].val << " ";

    return 0;
}