최대공약수

1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 분석 사이클이 없는 트리 구조이므로 임의의 노드에서 DFS를 진행하면서 해결 DFS 과정에서 유클리드 호제법을 사용해 비율들의 최소공배수와 최대공약수를 구하고, 재료의 최소 질량을 구하는데 사용 풀이 """ 칵테일에 들어가는 재료 N개는 공개되어 있다. 총 재료 쌍 N-1개의 비율이 입력으로 주어진다. 칵테일을 만드는데 필요한 각 재료의 양 이때, 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 한다. a b p q : a번 재료의 질량을 b번 재료의 질량으..