[1033] 칵테일 (C++)

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;
typedef long long ll;

vector<tuple<int, int, int>> A[10];

ll gcd(ll a, ll b);
void DFS(int node);
ll ratio[10];
bool visited[10];
ll lcm;

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

    int n; cin >> n;
    lcm = 1;

    for (int i = 0; i < n - 1; i++) {
        int a, b, p, q; cin >> a >> b >> p >> q;
        A[a].push_back(make_tuple(b, p, q));
        A[b].push_back(make_tuple(a, q, p));

        lcm *= (p * q / gcd(p, q));
    }

    ratio[0] = lcm;
    DFS(0);
    ll tmp = ratio[0];

    for (int i = 1; i < n; i++)
        tmp = gcd(tmp, ratio[i]);

    for (int i = 0; i < n; i++)
        cout << ratio[i] / tmp << " ";

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

void DFS(int node) {
    visited[node] = true;

    for (tuple<int, int, int> i : A[node]) {
        int next_node = get<0>(i);

        if (!visited[next_node]) {
            ratio[next_node] = ratio[node] * get<2>(i) / get<1>(i);
            DFS(next_node);
        }
    }
}

 

1. 인접리스트를 생성하여 p, q값도 함께 저장한다

2. 값을 받아옴과 동시에 LCM을 계속 업데이트 해준다

3. 초기 노드를 0으로 설정하고 LCM을 지정해준다

4. DFS를 진행하며 다음 노드의 값에 이전 노드의 값과 비율을 곱하여 저장한다

5. 각 노드의 값이 저장된 ratio 배열의 각 항에 GCD를 나누어 출력한다

 

 

 

 

---

인접리스트를 사용한 DFS와 GCD를 사용해야하는 문제이다.

비율을 저장하기 위해 인접리스트를 사용하고, DFS 또는 BFS를 사용해 탐색한다.

상대적으로 DFS의 구현이 더 간단하므로 DFS를 사용했다.

풀이 방식은 금새 생각해 낼 수 있지만, 슈도코드를 짜는 것 부터 구현하기까지가 어려운 문제였다.