https://www.acmicpc.net/problem/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를 통해 원소를 추가할 수 있다.
'코딩 > 백준' 카테고리의 다른 글
[백준]1516번 게임 개발 - C++/Java (0) | 2022.07.27 |
---|---|
[백준]1167번 트리의 지름 - C++/Java (0) | 2022.07.26 |
[백준] 9466번 - 텀 프로젝트 - C/C++ (0) | 2022.07.21 |
[백준]2473번 세 용액 - C/C++ (2) | 2022.07.19 |
[백준]1256번 사전 - C/C++/JAVA (2) | 2022.07.18 |