[백준 1033번] 칵테일 (C++)

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

 

1:3, 4:7 등 여러 비율이 주어지고 결국 이어지는 길목을 똑같이 이어줘야하는 문제이다. 

 

 

만약 

1번 : 2번 = 4 : 7

2번 : 3번 = 3 : 10

 

이라하면 1번 : 2번 : 3번이 성립하는데 비율이 다르기 때문에 이것을 통일해줘야한다.

2번이 처리해야하는 비율은 3과 7이다. 그렇다면 21로 비율을 맞출 수 있다. 21로 맞추면 1번에는 x3을 해줘야하고 10에는 x7을 해줘야한다.

 

그렇다면 

 

12 : 21 : 70

 

이고 이것이 정답이다. 만약  2번:4번 = 5 : 3 이라면 2번은 3,5,7을 갖고있고 이것을 통일해야한다. 

문제는 가장 적은 비율을 요구한다. 그러므로 최소공배수를 구해야한다는 것을 알 수 있다. 

 

또한 문제가 주어질 때 1:2 로 주어지지 않고 2:4로 주어지기도 한다. 그래서 두 수의 최대공약수로 나누어줘야한다,

 

https://tigerfrom2.tistory.com/70

유클리드 호제법(Euclidean algorithm) - 최대공약수, 최소공배수 알고리즘

 

그리고 각 번호를 그래프로 이어준 후 만약 N번 노드의 비율이 2,3,4 -> 12 로 통일된다면 2 쪽의 그래프는 전부 x6을 해주고 3은 x4를 해주는 식으로 그래프 순회를 돌아주면 되는 문제다.

 

사실 문제가 엄청 어렵진 않은데 그래프를 구성해서 구현하는 것이 생각보다 어려웠다. 필요한 것을 정확히 파악하고 그래프를 어떻게 구성해야할지 파악하는 것이 중요한 문제이다. 그리고 값이 integer를 넘어갈수도 있으니 long long으로 처리해주자

 

#include <iostream>
#include <queue>
#include <cstring>
#define ll long long
using namespace std;

ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b, a % b);
}

ll lmc(ll a, ll b){
    return a * b / gcd(a, b);
}

struct nodeInfo{
    int youNode;
    ll meRatio;
};

vector<nodeInfo> node[11];

void bfs(ll n, ll lmcValue){
    bool visited[11]; 
    memset(visited, false, sizeof visited);

    queue<pair<ll, ll>> q;
    visited[n] = true;

    for(int i = 0; i < node[n].size(); i++){        
        //cout << "큐삽입:: " << node[n][i].youNode << ' ' << lmcValue / node[n][i].meRatio << endl;

        q.push({node[n][i].youNode, lmcValue / node[n][i].meRatio});

        node[n][i].meRatio = lmcValue;
        visited[node[n][i].youNode] = true;
    }

    //cout << "exe :: " << n << ' ' << lmcValue << endl;

    while(!q.empty()){
        ll nowNode = q.front().first;
        ll nowValue = q.front().second;      
        q.pop();

        //cout << nowNode << ' ' << nowValue << endl;

        for(int i = 0; i < node[nowNode].size(); i++){
            ll next = node[nowNode][i].youNode;
            node[nowNode][i].meRatio *= nowValue;
            //cout << "노드넘버 : " << nowNode << ' ' << nowValue << ' ' << node[nowNode][i].meRatio << ' ' << endl;

            if(!visited[next]){          
                //cout << "큐삽입 :: " << next << ' ' << nowValue << endl;  
                q.push({next, nowValue});
                visited[next] = true;
            }
        }
    }
}

int main(){
    int N; cin >> N;

    if(N == 1) {
        cout << 1 << endl;
        return 0;
    }

    for(int i = 0; i < N - 1; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;

        ll gcdValue = gcd(c, d);

        nodeInfo n1;
        n1.youNode = b;
        n1.meRatio = c / gcdValue;

        nodeInfo n2;
        n2.youNode = a;
        n2.meRatio = d / gcdValue;

        node[a].push_back(n1);
        node[b].push_back(n2);
    }

    for(int i = 0; i < N; i++){
        int lmcValue = 1;
        //cout << endl;
        for(int j = 0; j < node[i].size(); j++){
            //cout << node[i][j].meRatio << ' ';
            nodeInfo ni = node[i][j];
            lmcValue = lmc(lmcValue, ni.meRatio);
        }
        //cout << "최소공배수 :: " << lmcValue << endl;
        //cout << i << ' ' << node[i].size() << ' ' << lmcValue << endl;

        if(lmcValue == 1) {
            continue;
        }
        bfs(i, lmcValue);
    }

    if(N > 1){
        int gcdV = node[0][0].meRatio;
        for(int i = 1; i < N; i++){
            gcdV = gcd(gcdV, node[i][0].meRatio);
        }

        for(int i = 0; i < N; i++){
            cout << node[i][0].meRatio / gcdV << ' ';
        }
    }
}