1167. Minimum Cost to Connect Sticks

[altay9]

Bir miktar sopanın uzunluklarını tutan bir array veriliyor. Array'in herhangi bir indexinde, o indexle gösterilen sopanın uzunluğu var.

Bu sopaları birbirleri ile birleştirip tek bir sopa hâline getireceğiz. Ama, herhangi iki sopayı birleştirmenin bir maliyeti var. Mesela x uzunluğunda bir sopa ile y uzunluğunda bir sopayı birleştirmek için x+y toplamı kadar maliyet ödememiz gerekecek.

Demek ki bizden istenen, en az mâliyetle bu sopaları birleştiren bir algoritma yaratmak.

Şu uzunluklara sahip üç sopa olduğunu düşünelim : [2,4,3]

Bunları en az mâliyetle ikişer ikişer birleştirmek için şu adımları izleriz: 2 + 3 = 5 (yeni sopa 5 uzunluğunda olacağı için, ilk maliyetimiz bu) 5 + 4 = 9 (ilk maliyete ek olarak bir de 9 ödememiz gerekecek)

Dolayısı ile toplam maliyet minimum 5 + 9 = 14 olur.

[ErdemT09]

Uzunluk olarak z>y=x çubukları var diyelim. Bunları birleştirmek için olan 2 yoldan: (x+y)+((x+y)+z)=2(x+y)+z < (x+z)+((x+z)+y)=2(x+z)+y Yani her zaman en küçükleri birleştirmeliyiz.

[ErdemT09]

Solved: https://github.com/spiralgo/algorithms/blob/master/src/main/java/algorithms/curated170/medium/MinimumCostToConnectSticks.java

[ErdemT09]

https://www.geeksforgeeks.org/optimal-file-merge-patterns/amp/ Nearly the same problem.