[백준] 칵테일 c++

칵테일

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

7312

2315

1806

33.922%

문제

 

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번 재료부터 순서대로 공백으로 구분해 출력한다.

---

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
using namespace std;

long long ans[10];
//tuple을 이용해 3개의 값을 저장할 수있도록 선언
vector <tuple<int, int, int>> adj[10];
bool visited[10];

//유클리드 호제법을 이용한 최대 공약수 구하는 함수
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	return GCD(b, a % b);
}

void DFS(int node)
{
	visited[node] = true;

	for (tuple<int, int, int> i : adj[node])
	{
		int next = get<0>(i);

		if (false == visited[next])
		{
			ans[next] = ans[node] * get<2>(i) / get<1>(i);
			DFS(next);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	long long tot_lcm = 1;
	cin >> n;

	//트리형식으로 이어질 수 있도록 설정
	for (int i = 0; i < n - 1; i++) {
		long long a, b, p, q;
		cin >> a >> b >> p >> q;
		adj[a].push_back({ b, p, q });
		adj[b].push_back({ a, q, p });
		tot_lcm *= p * q / GCD(p, q);
	}

	ans[0] = tot_lcm;
	DFS(0);
	long long ans_gcd = ans[0];

	for (int i = 1; i < n; i++)
	{
		ans_gcd = GCD(ans_gcd, ans[i]);
	}

	for (int i = 0; i < n; i++)
	{
		cout << ans[i] / ans_gcd << ' ';
	}
}

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