[백준 / BOJ] 1033 칵테일 (Java)

문제

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

1033번: 칵테일

august14는 세상에서 가장 맛있는 칵테일이다. 

이 칵테일을 제조하기위한 재료의 갯수 N과 각 재료의 비율이 주어졌을때, 

칵테일을 만들기위해 필요한 재료의 질량을 출력하는 문제다.

---

풀이

유클리드 호제법을 응용해서 푸는 수학 문제였다.

 

문제에서 두가지 재료의 비율이 주어진다.

이 비율을 갖고 각 재료의 질량을 구하는 공식을 만들어보면,

재료를 각각 a,b 비율을 p,q라 했을때,

 

1. 재료 a의 질량 = 재료b의 질량 * 재료a의 질량 * p

2. 재료 b의 질량 = 재료a의 질량 * 재료b의 질량 * q

 

가 된다. 이때, 재료 a와 b가 늘어남에따라 각 재료들에 연결된 다른 재료들또한 업데이트 해줘야한다.

재료 a와 재료 b사이의 비율을 유지하기위해 각 재료에 곱한값을 연결된 재료들에 각각 곱해주자.

 

관련 소스코드

    private void calc(int a, int b, long p, long q){
        Boolean[] check = new Boolean[N+5];
        long tempA = nums[a];
        long tempB = nums[b];
        update(a, tempB*p, check);
        update(b, tempA*q, check);
        edge.get(a).add(b);
        edge.get(b).add(a);
    }
    
    private void update(int target, long num, Boolean[] check){
        nums[target] *= num;
        check[target] = true;
        for(int i = 0; i < edge.get(target).size(); i++){
            if(check[edge.get(target).get(i)] != null) continue;
            update(edge.get(target).get(i), num, check);
        }
    }

nums에는 재료들의 질량이 업데이트 되어있다.

check는 양방향 간선을 타고 이미 업데이트해준 재료를 한번 더 업데이트해주지 않기위해 만들었다.

 

이 과정에서 p,q의 최대공약수를 구해 나눠준값을 곱해줘도 상관없으나 무의미하다. (결국 마지막에 모든 재료들의 최대공약수를 구해야하기때문..)

 

위 로직을 그대로 수행하면 각 재료들의 질량을 구할수있다.

마지막으로 모든 재료들의 최대공약수를 구한후 나눠주면 답이된다.

 

모든 재료들의 최대공약수를 구하고 나누는 소스코드

    private void setNums(){
        long gcd = getGCD(nums[0], nums[1]);
        while(gcd > 1){
            for(int i = 0; i < N; i++) gcd = getGCD(gcd, nums[i]);
            for(int i = 0; i < N; i++) nums[i] /= gcd;
        }
    }

 

수학문제에 약해서 푸는데 시간이 좀 걸린문제였다.

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/1033%20%EC%B9%B5%ED%85%8C%EC%9D%BC/Main.java

devxb/JJUNalgo