[Do It! 코딩테스트 자바편(김종관)] 문제 044(백준 1033번)

난이도

그냥 어려웠다. 도중에 풀다가 안 될 것 같아서 교재 풀이를 보았다. 이해는 그렇게 어렵지 않았다. 하지만 지금 내 수준으로는 골드 문제는 거의 못 풀 것 같다.

문제

칵테일 만들기(백준: 1033번)

풀이

import java.util.*;

public class MainTest {
  static ArrayList<cNode>[] A;
  static long lcm;
  static boolean visited[];
  static long D[];

  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    A = new ArrayList[N];
    visited = new boolean[N];
    D = new long[N];

    lcm = 1;
    for (int i = 0; i < N; i++) {
      A[i] = new ArrayList<cNode>();
    }
    for (int i = 0; i < N - 1; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      int p = sc.nextInt();
      int q = sc.nextInt();
      A[a].add(new cNode(b, p, q));
      A[b].add(new cNode(a, q, p));
      lcm *= (p * q / gcd(p, q)); // 두 수의 최소 공배수는 두수의 곱을 최대 공약수로 나눈 것입니다.
    }
    D[0] = lcm;
    DFS(0);
    long mgcd = D[0];
    for (int i = 1; i < N; i++) {
      mgcd = gcd(mgcd, D[i]);
    }
    for (int i = 0; i < N; i++) {
      System.out.print(D[i] / mgcd + " ");
    }
  }

  public static long gcd(long a, long b) {
    if (b == 0)
      return a;
    else
      return gcd(b, a % b);
  }

  public static void DFS(int node) { // DFS구현
    visited[node] = true;
    for (cNode i : A[node]) {
      int next = i.getB();
      if (!visited[next]) {
        D[next] = D[node] * i.getQ() / i.getP(); // 주어진 비율로 다음 노드 값 업데이트
        DFS(next);
      }
    }
  }
}

class cNode {
  int b;
  int p;
  int q;

  public cNode(int b, int p, int q) {
    super();
    this.b = b;
    this.p = p;
    this.q = q;
  }

  public int getB() {
    return b;
  }

  public int getP() {
    return p;
  }

  public int getQ() {
    return q;
  }
}