[백준 1033] 칵테일 (C#, C++) - soo:bak

문제 링크

1033번 - 칵테일

설명

N개의 재료로 칵테일을 만들 때, N-1개의 비율 관계가 주어집니다. 모든 재료의 질량을 정수로 하면서 총합이 최소가 되도록 각 재료의 질량을 구하는 문제입니다.

접근법

재료 간의 비율 관계를 그래프로 나타내면 트리 구조가 됩니다. 두 재료 a와 b의 비율이 p:q라면, a에서 b로 가는 간선에는 q/p 배율을, b에서 a로 가는 간선에는 p/q 배율을 저장합니다.

한 재료의 질량을 정하면 나머지 재료의 질량은 비율에 따라 자동으로 결정됩니다. 트리의 한 노드를 루트로 잡고 깊이 우선 탐색을 하면서 각 재료의 질량을 계산합니다. 부모 재료의 질량에 간선의 배율을 곱하면 자식 재료의 질량이 됩니다.

문제는 모든 재료가 정수 질량을 가져야 한다는 점입니다. 비율이 분수로 표현되기 때문에 시작 재료의 질량을 잘 선택해야 합니다. 모든 간선의 분모와 분자가 나누어떨어지도록, 시작 재료의 질량을 모든 비율 값들의 최소공배수로 설정합니다. 정확히는 각 간선의 p와 q를 최대공약수로 나눈 뒤 곱한 값들을 모두 곱합니다.

이렇게 계산하면 모든 재료가 정수 질량을 갖지만, 최소 비율은 아닐 수 있습니다. 모든 질량의 최대공약수로 나누면 최소 정수 비율을 얻습니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  struct Edge { public int to; public long num, den; }
  static List<Edge>[] adj = Array.Empty<List<Edge>>();
  static long[] mass = Array.Empty<long>();

  static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);

  static void Dfs(int v, int parent) {
    foreach (var e in adj[v]) {
      if (e.to == parent) continue;
      mass[e.to] = mass[v] * e.num / e.den;
      Dfs(e.to, v);
    }
  }

  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    adj = new List<Edge>[n];
    for (var i = 0; i < n; i++) adj[i] = new List<Edge>();

    var lcm = 1L;
    for (var i = 0; i < n - 1; i++) {
      var parts = Console.ReadLine()!.Split();
      var a = int.Parse(parts[0]);
      var b = int.Parse(parts[1]);
      var p = int.Parse(parts[2]);
      var q = int.Parse(parts[3]);
      var g = Gcd(p, q);
      var mul = (long)p / g * q;
      lcm *= mul;
      adj[a].Add(new Edge { to = b, num = q, den = p });
      adj[b].Add(new Edge { to = a, num = p, den = q });
    }

    mass = new long[n];
    mass[0] = lcm;
    Dfs(0, -1);

    var gAll = mass[0];
    for (var i = 1; i < n; i++) gAll = Gcd(gAll, mass[i]);

    for (var i = 0; i < n; i++) {
      Console.Write(mass[i] / gAll);
      Console.Write(i + 1 == n ? "\n" : " ");
    }
  }
}

C++

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

typedef long long ll;
typedef vector<ll> vl;

struct Edge { int to; ll num, den; };

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

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

  int n; cin >> n;
  vector<vector<Edge>> adj(n);
  ll lcm = 1;
  for (int i = 0; i < n - 1; i++) {
    int a, b, p, q; cin >> a >> b >> p >> q;
    ll g = gcd(p, q);
    lcm *= (ll)p / g * q;
    adj[a].push_back({b, q, p});
    adj[b].push_back({a, p, q});
  }

  vl mass(n);
  mass[0] = lcm;
  function<void(int,int)> dfs = [&](int v, int parent) {
    for (auto &e : adj[v]) {
      if (e.to == parent) continue;
      mass[e.to] = mass[v] * e.num / e.den;
      dfs(e.to, v);
    }
  };
  dfs(0, -1);

  ll gAll = mass[0];
  for (int i = 1; i < n; i++) gAll = gcd(gAll, mass[i]);

  for (int i = 0; i < n; i++)
    cout << mass[i] / gAll << (i + 1 == n ? '\n' : ' ');

  return 0;
}