이동식 저장소

골2~플5 중 100명 이상 푼 문제를 풀고 있다.

칵테일의 재료 간 비율이 주어질 때, 각 재료의 양을 구해야 하는 문제이다. 이때 무게의 합이 가장 작아야 하므로 최소공배수를 이용하여 비율을 적절히 나누어야 한다.

$a:b=p:q$인 $a$와 $b$의 쌍은 무한히 많지만, 가장 쉬운 쌍으로는 $(a,b)=(ab\ast p,ab\ast q)$가 있다. 우선 모든 무게를 1로 초기화한 다음 계산해 나가면 된다. 무게의 범위가 int 범위를 초과할 수 있으므로 64비트 정수형을 써야 안전하다.

그런데 $a$와 $b$만 바꿔서는 안 된다. 이미 이전에 $a$ 또는 $b$와의 비율이 정해진 경우가 있기 때문이다. 예를 들어, 문제의 예제 중 세 번째 줄 4 1 3 1을 수행할 때는 4번 재료와 1번 재료뿐만 아니라 이전에 4번 재료와 비율이 정해져 있는 0번 재료에도 $a$의 변화를 동일하게 적용시켜야 한다. 만약 $a$에 10을 곱해야 한다면, $a$와 비율이 연동된 모든 값에도 10을 곱해야 한다는 뜻이다.

정답을 출력하기 전에 주의할 점이 있다. 위에서는 $a$와 $b$를 아주 단순하게 계산했으므로, $a$와 $b$가 서로소라는 보장이 없다. 따라서 모든 재료 값의 최소공배수($gcd$)를 구한 다음, 모든 값을 $gcd$로 나누어야 정답을 구할 수 있다. 모든 값을 나눠야 하는 이유는 재료 비율의 쌍이 $n-1$개 주어지므로 모든 재료의 비율이 연동되기 때문이다.

어째서인지 런타임 에러가 엄청나게 났다.. 아마도 std::set의 합병과 관련이 있지 않나 싶다.