[Python] 프로그래머스 135808. 과일장수 (Lv.1)

https://school.programmers.co.kr/learn/courses/30/lessons/135808

프로그래머스

 

간단한 그리디 유형의 문제입니다. 사과를 m개씩 묶어서 팔아야 하는데 m개 중 `가장 낮은 점수 x m`의 가격을 받을 수 있습니다. 간단하게 사과를 내림차순으로 정렬하고 앞에서 부터(점수가 높은 사과부터) m 개씩 끊어가며 판매하면 됩니다. 

 

예시를 통해 검증을 해보겠습니다. 예시 1번에서 사과의 점수가 [1, 2, 3, 1, 2, 3]이고 4개씩 묶어 팔아야 한다고 합니다. 이를 내림차순으로 정렬하면 [3, 3, 2, 2, 1, 1]이 되고 얻는 가격은 앞에서부터 4개를 선택해 얻은 [3, 3, 2, 2]에서 가장 낮은 점수인 2 x 4 = 8입니다. 

 

사과 n개가 존재하고 이를 내림차순으로 정렬한 값이 [A1, A2, A3, ...Am, ... An]이라고 해 봅시다. 내림차순으로 정렬했기 때문에 각 사과들의 가격은 A1 >= A2 >= A3 ...>= Am... >= An의 대소를 가집니다. 앞에서부터 m개의 사과를 선택했을 때 얻는 금액은 `Am x m` 입니다. Am보다 가격이 작거나 같은 어떤 사과 Ax (m < x <= n)를 선택하면 얻는 금액은 `Ax x m`이 됩니다. Am >= Ax이므로 m을 곱해봐야 대소관계가 변하지 않음을 알 수 있습니다. 따라서 매 순간마다 가능한 사과들 중에 가격이 큰 m개를 순서대로 고르는것이 가격합을 가장 크게 만드는 방법입니다.

 

def solution(k, m, score):
    score.sort(key = lambda x : -x)
    
    answer, i = 0, m - 1
    
    while i < len(score):
        answer += score[i] * m
        i += m
    
    return answer