[백준] 1033번 칵테일 - C/C++/Java

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

1033번: 칵테일

문제

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보다 작거나 같은 자연수이다.

출력

첫째 줄에 칵테일을 만드는데 필요한 각 재료의 질량을 0번 재료부터 순서대로 공백으로 구분해 출력한다.

---

 

    모든 노드는 val이 1 인 상태로 시작한다. 주어진 비율이 9:6과 같이 주어졌을 때 비율을 최대 공약수로 나누어 3:2와 같이 바꾼다. 기존에 두 값이 변한 적이 없어 val 이 1이라면 단순히 a 기준 값들을 3배 b 기준 값들을 2배 해주면 된다. 하지만 기존에 a와 b 가 앞선 작업들로 바뀌어 a.val = 7 , b.val = 4 과 같이 되어 있다면 실제 값은 7x ,4y 이다 이 값들이 3 : 2 비율 인 것이므로 7x : 4y = 3 : 2 ; 12y = 14 x ; 6y = 7x ; x=6 y=7이면 방정식이 참이 된다. 그러므로 a 와 연결되어 있던 노드들은 6을 곱해주고 b와 연결된 노드들은 7을 곱해주면 a : b = 42 : 28로 3:2 비율이 맞춰지며 나머지 연관되어 있는 노드들의 비율도 적절하게 조정된다. 

   

    따라서 진행할 작업을 순서대로 나열한다면

1) p : q를 최대 공약수(gcd)로 나눈 비율로 바꾸어 준다.

2) a와 연관이 있는 노드들과 b와 연관이 있는 노드들에 곱할 값을 구한다.

    - a 에는 arr[b].val * p / gcd(p, q);                           // 4 * 9 / 3 => 12

    - b 에는 arr[a].val * q / gcd(p, q);                           // 7 * 6 / 3 => 14

3) 곱할 값들을 최대 공약수로 나누어 준다.              // 6, 7

4) 각각 a와 b 에 연관된 노드들에 3)에서 구한 값들을 곱해준다.

5) a 와 b를 연결해준다. 

#include <iostream>
#include <vector>

using namespace std;

struct mat {
	int val=1;
	vector<int> edge;
}arr[11];

int vis = 0;

int gcd(int a, int b) {
	return b ? gcd(b,a % b) : a;
}

void update(int node, int mod) {
	arr[node].val *= mod;
	vis |= (1 << node);
	for (auto e : arr[node].edge) {
		if (!(vis & (1 << e))) {
			update(e, mod);
		}
	}
}

int main() {
	int n,a,b,p,q,gcdVal,amod,bmod;
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		cin >> a >> b >> p >> q;
		gcdVal = gcd(p, q);
		amod = arr[b].val * p / gcdVal;
		bmod = arr[a].val * q / gcdVal;
		gcdVal = gcd(amod, bmod);
		vis = 0;
		update(a, amod/gcdVal);
		update(b, bmod/gcdVal);
		arr[a].edge.push_back(b);
		arr[b].edge.push_back(a);
	}

	for (int i = 0; i < n; i++)
		cout << arr[i].val << " ";
	return 0;
}

package test;
import java.util.*;

class mat {
	int val;
	ArrayList<Integer> edge;
	mat() {
		this.val = 1;
		this.edge = new ArrayList<Integer>();
        
	}
}

public class Main {
	static mat[] arr = new mat[11];
	static int vis = 0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n,a,b,p,q,gcdVal,amod,bmod;
		n = sc.nextInt();
		for(int i=0;i<n;i++) {
			arr[i] = new mat();
		}
		for (int i = 0; i < n-1; i++) {
			a = sc.nextInt(); b = sc.nextInt();
			p = sc.nextInt(); q = sc.nextInt();
			gcdVal = gcd(p, q);
			amod = arr[b].val * p / gcdVal;
			bmod = arr[a].val * q / gcdVal;
			gcdVal = gcd(amod, bmod);
			vis = 0;
			update(a, amod/gcdVal);
			update(b, bmod/gcdVal);
			arr[a].edge.add(b);
			arr[b].edge.add(a);
		}
		
		for(int i=0;i<n;i++) {
			System.out.print(arr[i].val + " ");
		}
	}
	
	public static int gcd(int a , int b) {
		if(b == 0) return a;
		else return gcd(b, a % b);
	}
	public static void update(int node,int mod) {
		arr[node].val *= mod;
		vis |= (1 << node);
		for (int e : arr[node].edge) {
			if ((vis & (1 << e)) == 0) {
				update(e, mod);
			}
		}
	}
}

---

    해야 할 단계가 많은 문제였다. 깔끔하게 해야 할 단계들을 정리하고 하면 쉽지만 눈앞에 닥친 문제만 풀려고 하면 풀기 힘든 문제였다. 각 노드에 어떤 숫자를 곱해주어야 하는지를 정확하게 정하고 간다면 쉽게 풀 수 있을 것 같다. 같은 문제를 자바로도 풀어보았다. 자바는 boolean과 int과 엄격하게 나눠져 있어 gcd 함수를 조금 바꾸었다. 또한 자바에도 Vector 가 존재하는데 이와 유사한 ArrayList 도 있어 어느 것을 사용해야 하는지 알아보았다. Vector는 Thread Safe 하여 멀티 스레딩이 사용될 때 사용하는 것이 좋고 ArrayList는 Thread Safe 하지 않은 대신 속도가 빠르기 때문에 스레드와 상관이 없는 일을 할 때 사용된다고 한다. 코딩 테스트 문제에서는 ArrayList를 주로 사용하면 될 것 같다. 유의해야 할 부분은 이 ArrayList를 선언할 때 한번 new로 생성을 하고 다시 한번 arr[i] = new mat() 을 해줘야 에러가 나지 않는다. 또한, C++ 의 vector의 push_back처럼 Java의 ArrayList는 add를 통해 원소를 추가할 수 있다.