백준 1033.cpp [칵테일]

풀이

만약 a, b, p, q 가 다음과 같다고 한다면 [3, 9, 2, 3]

 

a(3) : b(9) = p(2) : q(3)를 만족해야 한다. (여기서 a, b의 값은 재료의 질량이다)

즉 pb * x == qa * y를 만족해야 한다.

그럼 (lcm은 최소공배수, gcd는 최대공약수이다)
x 
= lcm / pb 
= (qa * pb) / gcd / pb 
= qa / gcd
= 1

y 
= lcm / qa 
= (qa * pb) / gcd / qa 
= pb / gcd
= 2

위처럼 x, y를 구할 수 있다.

그런데 이때 x, y에 최대공약수가 존재할 수 있다.

우리는 최소가 되는 결과값을 원하기 때문에 최대공약수가 있다면 해당 값으로 나누어줘야 한다.

따라서 x, y의 gcd를 구하여 나누어준다음 다른 비율들에 영향을 주지 않기 위해서

해당 노드와 연결되어 있는 모든 노드에 같은 값을 곱하여 업데이트해주면 된다.

즉 b와 연결되어 있는 모든 노드에는 x를 곱해주고,

a와 연결되어 있는 모든 노드에는 y를 곱해준다.

혹시나 중복해서 곱해지지 않도록 방문처리를 해준다.

 

전파가 끝이나면 a와 b를 연결해준다.

 

이렇게 푼다면 int 자료형으로도 원하는 답을 구할 수 있다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool visited[11];
int ans[11];
vector<int> edges[11];

int getGcd(int a, int b) {
    int r;
    
    if(a < b) {
        r = a;
        a = b;
        b = r;
    }

    while(b != 0) {
        r = a % b;
        a = b; 
        b = r;
    }
    return a;
}
void update(int now, const int& val) {
    visited[now] = true;
    ans[now] *= val;

    for(int next : edges[now]) {
        if(visited[next]) continue;

        update(next, val);
    }
}
int main() {ios_base::sync_with_stdio(0); cin.tie(NULL);
    int N;
    cin >> N;

    int a, b, p, q;

    fill_n(ans, N, 1);

    for(int i = 0; i < N - 1; i++) {
        cin >> a >> b >> p >> q;

        int gcd = getGcd(ans[a], ans[b]);
        int x = q * ans[a] / gcd;
        int y = p * ans[b] / gcd;

        gcd = getGcd(x, y);
        memset(visited, 0, sizeof(visited));

        update(b, x / gcd);
        update(a, y / gcd);

        edges[a].emplace_back(b);
        edges[b].emplace_back(a);
    }

    for(int i = 0; i < N; i++) { 
        cout << ans[i] << ' ';
    }
}