프로그래머스 Lv.1 | Python | 과일 장수

1. 문제 정보

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

프로그래머스

• 난이도: LV.1
• 풀이 시간: 20분

---

2. 문제 요약

사과는 1점부터 k점까지의 품질 점수를 가지며, m개씩 묶어 상자로 판매한다.

이때 한 상자의 가격은 다음 기준으로 결정된다.

• 상자 내 가장 낮은 점수 p × m

즉, 같은 개수로 묶더라도 최솟값이 낮아지면 전체 가격이 떨어지는 구조다.

---

3. 접근 기준

• 이 문제는 단순 구현이 아니라 어떤 기준으로 묶어야 이익이 최대가 되는지를 결정하는 문제다.

“각 상자의 최솟값을 최대화해야 전체 이익이 커진다”

---

4. 사용한 패턴 / 알고리즘

그리디(Greedy)

• 각 선택이 이후 결과에 직접 영향을 주는 구조
• “현재 기준에서 최적 선택(최솟값이 최대가 되도록 묶기)”을 반복하면 전체 최적이 되는 유형

---

5. 핵심 아이디어

• 가격은 “평균”이나 “합”이 아니라 최솟값으로 결정됨
• 따라서 높은 점수끼리 먼저 묶어야 박스의 최솟값이 유지됨
• 내림차순 정렬 후 m개씩 자르면
  → 각 그룹의 마지막 값이 해당 박스의 최솟값이 됨
• 남는 사과는 어떤 경우에도 이익에 기여하지 않으므로 제외

---

6. 풀이 코드

def solution(k, m, score):
    answer = 0
    score.sort(reverse=True)
    for i in range(0,len(score),m):
        if i+m>len(score):
            break
        answer+=(score[i:i+m][-1])*m
    return answer

---

7. 핵심 로직 요약

• 점수를 내림차순 정렬
• m개씩 묶어서 각 그룹의 마지막 값을 최솟값으로 사용
• (최솟값 × m)을 누적하여 총 이익 계산