백준 1033번 칵테일 (Java)

문제

백준 1033번 칵테일 / 골드2
august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다.
경근이는 인터넷 검색을 통해서 재료 쌍 N-1개의 비율을 알아냈고, 이 비율을 이용해서 칵테일에 들어가는 전체 재료의 비율을 알아낼 수 있다.
총 재료 쌍 N-1개의 비율이 입력으로 주어진다. 이때, 칵테일을 만드는데 필요한 각 재료의 양을 구하는 프로그램을 작성하시오. 이때, 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 한다. 칵테일을 만드는 재료의 양은 정수이고, 총 질량은 0보다 커야한다.
비율은 "a b p q"와 같은 형식이고, a번 재료의 질량을 b번 재료의 질량으로 나눈 값이 p/q라는 뜻이다.

입력

첫째 줄에 august14를 만드는데 필요한 재료의 개수 N이 주어지며, N은 10보다 작거나 같은 자연수이다.
둘째 줄부터 N-1개의 줄에는 재료 쌍의 비율이 한 줄에 하나씩 주어지는데, 문제 설명에 나온 형식인 "a b p q"로 주어진다. 재료는 0번부터 N-1까지이며, a와 b는 모두 N-1보다 작거나 같은 음이 아닌 정수이다. p와 q는 9보다 작거나 같은 자연수이다.

풀이

수학적으로 접근하는 방법을 고안하는 데 오래 걸렸던 문제이다. 각 두 재료의 비율들을 하나의 모든 재료의 비율로 변환하는 부분을 많이 고민했다. 알게 되면 별 것 아닌 것을...

우선 입력으로 들어오는 p와 q의 최대공약수gcd를 구해서 나누어주며 p와 q의 값을 간소화해 주었다. 이후, totalmul에 모든 비율의 곱을 구하며 재료의 양의 기준점을 세워주었다. 이렇게 되면 기준점을 중심으로 어떤 값을 나누어주고 곱해주더라도 자연수로 값이 계산된다.

이후에는 간단하다. 0번 재료를 기준으로 DFS방법으로 그래프를 순회하며 result배열에 기준점에 대한 재료의 비율을 저장해주었다. 그리고 마지막으로 칵테일을 만들기 위한 최소의 질량을 구하기 위해 result배열의 모든 수의 totalGCD를 유클리드 호제법을 사용해 구해주었고. result[idx] / totalGCD 출력해 주면 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        ArrayList<Node>[] graph = new ArrayList[N];
        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<Node>();
        }

        StringTokenizer st;
        long totalmul = 1;
        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());

            long gcd = getGCD(p, q);
            p /= gcd;
            q /= gcd;
            graph[a].add(new Node(b, p, q));
            graph[b].add(new Node(a, q, p));
            totalmul *= (p * q);
        }

        long[] result = new long[N];
        boolean[] visit = new boolean[N];
        result[0] = totalmul;
        dfs(graph, result, visit, 0);

        long totalGCD = result[0];
        for (int i = 1; i < result.length; i++) {
            totalGCD = getGCD(totalGCD, result[i]);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < result.length; i++) {
            result[i] /= totalGCD;
            sb.append(result[i]).append(" ");
        }
        System.out.println(sb.toString());
    }

    static long getGCD(long a, long b) {
        if (b == 0)
            return a;
        return getGCD(b, a % b);
    }

    static void dfs(ArrayList<Node>[] graph, long[] result, boolean[] visit, int start) {
        visit[start] = true;

        for (Node n : graph[start]) {
            if (visit[n.t])
                continue;
            result[n.t] = result[start] / n.p * n.q;
            dfs(graph, result, visit, n.t);
        }
    }
}

class Node {
    int t;
    int p;
    int q;

    Node(int t, int p, int q) {
        this.t = t;
        this.p = p;
        this.q = q;
    }
}