Algorithm/Acmicpc
1033 칵테일 [JAVA]
문제분석https://www.acmicpc.net/problem/10330~N-1의 인덱스 사이의 비율 p/q를 주고이걸 바탕으로 각 인덱스에 해당하는 재료를 정수로 만들었을 때 그 합이 최소가 되게 만들라는 문제다. 따라서1. 인덱스 0과 연결된 노드는 최소 1개 이상 존재하기 때문에 (칵테일을 제조할 수 있다는 전제가 있음) 해당 노드를 찾아 두 노드를 기준으로 삼는다 (비율이 p/q면 a,b의 질량을 p,q로 산정한다) (당연히 p,q는 서로소다)2. bfs로 인접 노드끼리 비교하며 모든 노드간 비율을 구한다.3. 유클리드 호제법을 통해 최소공배수를 구한다https://programmer-chocho.tistory.com/9 [JAVA] 최대 공약수(GCD), 최소 공배수(LCM) 구하기최대 공약수..
