BOJ_1033 : 칵테일

👉 문제링크

1033번: 칵테일

---

---

🔸 문제 분석 🔸

• 10 이하의 자연수 N이 주어지고, N-1 개의 재료 비율이 주어진다.
• 칵테일을 만드는데 필요한 각 재료의 최소 질량을 출력한다.

🔸 문제 풀이 🔸

• 기준값을 찾기 위해 입력된 p, q 비율들의 최소공배수를 구한다.
• N개의 재료와 N-1의 연결 정보는 N개의 노드와 N-1의 간선 정보이므로 트리 형태로 나타낼 수 있다.
  • 한 노드에 값을 넣고 DFS로 인접한 노드를 탐색하며 입력된 비율로 각 노드의 질량 값을 만들어 간다.
• 모든 노드의 값의 최대공약수를 다시 한번 계산한다.
• 구한 최대공약수로 노드의 값을 나눈 값을 출력한다.
  • 모든 재료의 합이 최소가 되면서 정수가 되도록 하기 위해 나눈다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static boolean[] visited;
    private static ArrayList<Node>[] adjlist;
    private static int N;
    private static long[] D;

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        visited = new boolean[N];
        adjlist = new ArrayList[N];
        D = new long[N];

        for (int i = 0; i < N; i++) {
            adjlist[i] = new ArrayList<>();
        }

        long lcm = 1;

        for (int i = 0; i < N - 1; i++) {
            StringTokenizer 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());
            adjlist[a].add(new Node(b, p, q));
            adjlist[b].add(new Node(a, q, p));
            lcm *= (long) p * q / gcd(p, q);
        }

        // DFS
        D[0] = lcm;
        dfs(0);
        long gcd = D[0];
        for (int i = 1; i < N; i++) {
            gcd = gcd(gcd, D[i]);
        }

        // Output
        StringBuilder sb = new StringBuilder();
        for (long i : D) {
            sb.append(i / gcd).append(' ');
        }
        bw.write(sb.toString());
        bw.flush();
    }

    private static void dfs(int now) {
        visited[now] = true;

        for (Node node : adjlist[now]) {
            if (!visited[node.num]) {
                D[node.num] = D[now] * node.numerator / node.denominator;
                dfs(node.num);
            }
        }
    }

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

    private static class Node {
        int num;
        int denominator;
        int numerator;

        public Node(int num, int denominator, int numerator) {
            this.num = num;
            this.denominator = denominator;
            this.numerator = numerator;
        }
    }
}

🔸 코드 해석 🔸

• N-1개의 재료 비를 입력받아 인접 행렬로 저장한다.
  • 이때 비율의 최소공배수를 계산한다.
  • 곱셈 누적으로 계산하므로 long형으로 계산해야 한다.
• 계산된 최소공배수를 초기값으로 재료(노드) 탐색을 진행한다.
  • 탐색하며 입력된 비율에 따라서 재료 별 질량 값을 D배열에 저장한다.
• 탐색 후 다시 한번 재료들의 질량 값으로 최대공약수를 계산한다.
• 최대공약수로 나눈 재료 질량값을 출력한다.

---

🔸 end 🔸

• N이 최대 10, p와 q가 최대 9여서 int형 범위로 괜찮을 것이라 생각했는데, 비율이 중첩되면 int 범위를 벗어날 수 있었다.
  • int로 내서 1회 틀리고, long으로 변경해 맞았다.
• 정답 해설을 보면서 풀이했는데, 최대공약수/최소공배수 뿐만 아니라 탐색까지 들어간 복합적인 문제였다.
  • 하지만 가장 어려웠던 건, 트리 구조로 이해하는 것이었다.