[HR] : Greedy Florist ★

https://www.hackerrank.com/challenges/greedy-florist/problem?isFullScreen=true

문제 설명

• c에 있는 element들은 flower들이고, 가격으로 표시되어있다. c = [2,5,6]이라면, 2달러짜리 꽃, 5달러짜리 꽃, 6달러짜리 꽃이 있는 것이다. 여러 사람들에 의해 꽃들이 적어도 한번씩 구매되도록 할 때, 전체 금액이 최소가 되도록 해라!

• len(c)는 구매할 꽃의 개수가 된다.

• k는 사람 수이다.

가격 정책 개념

• 같은 사람이 n 번째 꽃을 구매 할때는 n+1 배의 가격을 지불해야한다.

• 따라서 최대한 많은 사람들이 꽃을 사고,

• 가장 높은 가격의 꽃부터 구매해야 비용이 최소화 된다.

• c = [1,2,3,4], k=3 인 예제를 보면, 전체 꽃에 대해 cnt와 i 가 사람 수만큼 loop를 돌도록 해야한다.

c.pop 4 3 2 1
cnt   0 0 0 1
i     0 1 2 0

내가 짠 코드

def getMinimumCost(k, c):
    c = sorted(c)
    cnt = 0
    cost = 0
    while len(c) > 0:
        for i in range(k):
            if len(c) > 0:
                price = c.pop()
                cost += ((cnt+1) * price)
        cnt += 1
    return cost

개선 코드

def getMinimumCost(k, c):
    cost = 0
    for idx, price in enumerate(sorted(c, reverse=True)):
        # print(idx, idx%k, price)
        cost += (idx//k + 1) * price
    return cost