1033 칵테일 [JAVA]

문제분석

https://www.acmicpc.net/problem/1033

0~N-1의 인덱스 사이의 비율 p/q를 주고

이걸 바탕으로 각 인덱스에 해당하는 재료를 정수로 만들었을 때 그 합이 최소가 되게 만들라는 문제다.

 

따라서

1. 인덱스 0과 연결된 노드는 최소 1개 이상 존재하기 때문에 (칵테일을 제조할 수 있다는 전제가 있음) 해당 노드를 찾아 두 노드를 기준으로 삼는다 (비율이 p/q면 a,b의 질량을 p,q로 산정한다) (당연히 p,q는 서로소다)

2. bfs로 인접 노드끼리 비교하며 모든 노드간 비율을 구한다.

3. 유클리드 호제법을 통해 최소공배수를 구한다

https://programmer-chocho.tistory.com/9

[JAVA] 최대 공약수(GCD), 최소 공배수(LCM) 구하기

 

4. 해당 최소 공배수를 비율에 곱하여 각 비율을 정수로 만들어준다

 

여기서 정말 주의해야 하는 점은 N이 10이라는 거다.

너무나 작은 크기라 사실 아무생각 없이 LCM을 int형으로 구현했지만 잘 생각해보자.

 

0-1 : 10 : 1

1-2 : 10 : 1

...

이런식이라면?

ratio 0 : 10

ratio 1 : 1

ratio 2: 10^-1

...

ratio 9 : 10^-8

 

즉, 첫번째 재료는 10^9가 된다.

이 상태로 lcm을 구하게 되면 int*int 하는 순간 overflow가 발생하게 된다.

 

실제로 int형으로 해당 case를 만들어보면

이렇게 음수가 나와버리지만

 

long으로 만들면 overflow가 발생하지 않는다.

 

코드

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        Ratio[] ingredients = new Ratio[n];

        Ratio[][] links = new Ratio[n][n];

        //n is just 10
        for (int i = 1; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int top = sc.nextInt();
            int bottom = sc.nextInt();
            Ratio ratio = getRatio(top, bottom);
            links[a][b] = ratio;
            links[b][a] = getInverse(ratio);
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        for (int i = 1; i < n; i++) {
            if(links[0][i] != null){
                ingredients[0] = new Ratio(links[0][i].top, 1);
                ingredients[i] = new Ratio(links[0][i].bottom,1);
                queue.add(i);
                break;
            }
        }

        Set<Long> bottomSet =new HashSet<>();
        while (!queue.isEmpty()){
            Integer poll = queue.poll();

            for (int i = 1; i < n; i++) {
                if(links[poll][i] != null && ingredients[i] == null){
                    ingredients[i] = getRatio(ingredients[poll].top*links[poll][i].bottom, ingredients[poll].bottom*links[poll][i].top);
                    if(ingredients[i].bottom != 1)
                        bottomSet.add((long) ingredients[i].bottom);
                    queue.add(i);
                }
            }
        }
        long lcm = bottomSet.isEmpty() ? 1L : getLCM(bottomSet.toArray(new Long[0]));

        System.out.print(ingredients[0].top*(lcm/ingredients[0].bottom));
        for (int i = 1; i < n; i++) {
            System.out.print(" "+ingredients[i].top*(lcm/ingredients[i].bottom));
        }
        System.out.println();



    }

    static Ratio getRatio(int top, int bottom){
        int[] primes = {2,3,5,7};
        boolean isChanged = false;
        do {
            isChanged = false;
            for (int prime : primes) {
                if (top % prime == 0 && bottom % prime == 0) {
                    top /= prime;
                    bottom /= prime;
                    isChanged = true;
                    break;
                }
            }
        } while (isChanged);
        return new Ratio(top,bottom);
    }
    static Ratio getInverse(Ratio ratio){
        return new Ratio(ratio.bottom,ratio.top);
    }

    static class Ratio {
        int top, bottom;

        @Override
        public String toString() {
            return "Ratio{" +
                    "top=" + top +
                    ", bottom=" + bottom +
                    '}';
        }

        public Ratio(int top, int bottom) {
            this.top = top;
            this.bottom = bottom;
        }


    }

    public static long getLCM(Long[] arr) {
        if (arr.length == 1) {
            return arr[0];
        }

        long gcd = getGCD(arr[0], arr[1]);
        long lcm = (arr[0] * arr[1]) / gcd;

        for (int i = 2; i < arr.length; i++) {
            gcd = getGCD(lcm, arr[i]);
            lcm = (lcm * arr[i]) / gcd;
        }

        return lcm;
    }

    public static long getGCD(long num1, long num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
        return getGCD(num2, num1 % num2);
    }
}