백준 문제풀이 (Gold)

칵테일 G3

• 재료가 N개이고, 재료 쌍이 N-1 개 이므로 트리를 생각할 수 있음
• 임의 재료 하나에서 시작하여 나머지 재료를 모두 탐색하며 계산할 수 있음 (DFS)
• 처음 비율의 lcm 을 구한 후, 시작 재료의 값에 넣어줌
• 각 재료를 방문할때, 재료의 값은 부모재료 * q/p 가 됨
• 모든 재료 방문 후, 최소한의 값으로 구성해야 하므로, 모든 값의 gcd 를 구한 후, 나누어주면 됨.

solution