곤충 키우기 timer 1s memory 64MB

솔이는 솔향기 가득한 소나무숲에 가서 곤충을 채집하여 집에 데려와 기르는 것을 좋아한다.

솔이가 채집한 곤충들은 각각의 곤충 사육통에 들어가서 살게 된다.

곤충들은 살아있는 생명체기에 물을 공급받아야 한다.

사육통 안에 사는 곤충의 종류에 따라서, 사육통에 공급해야 하는 물의 양이 각각 다르다.

솔이의 입장에서 모든 곤충들에게 줘야 할 물의 양을 각각 재서 사육통에 공급하기는 너무 번거로운 일이므로,

솔이는 급수대에 물을 넣어 주면 각 사육통에 알아서 물을 공급해주는 특수한 장비를 이용하기로 했다.

예시로 그림 1을 보도록 하자.

그림 1

그림 1과 같은 경우는 3마리의 곤충이 사육되고 있는 경우이다.

곤충들은 물이 흐르는 파이프가 끝나는 3, 4, 5번 통에만 살고 있으며, 이를 사육통 이라고 하자.

1, 2번 통처럼 아래로 물이 흐를 수 있는 파이프가 연결되어 있는 경우는 곤충이 살지 않고, 물만 흐른다.

이를 물통이라고 하자.

1번 물통은 항상 가장 맨 위에 있으며, 솔이가 맨 처음 물을 넣어주는 급수대가 된다.

또한 파이프의 개수는 항상 물통의 수+사육통의 수-1개이며, 모든 통은 항상 파이프로 이어져 있다.

물통에 물이 들어오면, 중력에 의해서 자연스럽게 아래로 연결된 파이프로 물이 흐르는데, 물통에 들어있는 물×파이프에 써 있는 퍼센트만큼 물이 흐른다.

예를 들어, 그림 1에서 맨 처음 1번 통에 솔이가 공급한 물의 양이 8mL라고 가정하면, 2번 물통과 3번 사육통으로 흘러 들어가는 물은 각각 8mL ×​ 50% = 4mL이 된다.(50%는 50/100과 동일하다.)

마찬가지로 4번과 5번 사육통으로 흘러 들어가는 물은 각각4mL의 25%와 75%인 1mL와 3mL가 된다.

당연하지만, 한 물통에서 아래로 연결된 파이프의 퍼센트의 총합은 100%이다.

어떤 파이프는 첨단 과학력으로 만들어진 슈퍼 파이프이다.

슈퍼 파이프는 필요에 따라 전원을 키고 끌 수 있는데,

작동 중인 슈퍼 파이프는 질량 보존의 법칙을 무시하고 원래 흘러 들어오는 물의 제곱만큼을 아래의 물통에 보내준다.

(과학을 제대로 배운 사람이라면 이게 엄청나게 초-비현실주의적인 기술이란 것을 알고 있겠지만, 일단은 넘어가자.)

예컨대, 만약 그림 1에서 2번 물통에서 5번 사육통을 잇는 파이프가 슈퍼 파이프라면, 5번 사육통으로 흘러들어가는 물은 원래의 3mL의 제곱인 9mL가 된다.

각 사육통마다 공급받아야 하는 물의 양인 정량이 다른데, 정량 이상이 공급되기만 하면 된다.

전체 장비의 구조와 각 사육통마다 공급 받아야 하는 물의 양이 주어질 때, 솔이가 급수대(1번 물통)에 넣어야 하는 물의 총량의 최솟값을 구하는 프로그램을 작성하시오.