Greedy Florist

def getMinimumCost(k, c):
    total = 0
    counter = 0
    length = len(c)
    c.sort(reverse=True)

    for i in range(0, length):
        total += (counter + 1) * c[i]
        if length != k and (i + 1) % k == 0:
            counter += 1

    return total

 

탐욕 알고리즘 문제는 복잡한 문제는 안나온다. 항상 제일 높은, 비싼 비용을 먼저 선택하는 방식으로 구현하기 때문이다.

 

이 문제는 로직은 잘 만들었는데 반복문을 돌 때 역순, i의 초기값을 길이-1로 시작했다가 계속 테스트 케이스를 통과를 못해서 오류를 찾는데 한참이나 걸렸다.

간단하게 k 값이 2이고 길이가 10이면, 2명이 지나고 나서 카운트가 올라야 하는데 1명이 지나고 바로 카운트가 바뀌게 되는 오류가 생기게 된다.

 

다시 한번 느끼는 루프 불변성의 중요성