< 프로그래머스 C++ > 과일 장수

문제 설명

과일 장수가 사과 상자를 포장하는 문제

• 사과는 1점부터 k점까지의 점수로 분류 (k점이 최상품)
• 한 상자에 사과 m개씩 담아서 포장
• 상자에 담긴 사과 중 가장 낮은 점수가 p점이면 한 상자 가격은 p × m
• 남는 사과는 버림

최대 이익을 구하는 문제

예시

항목 값

k	3
m	4
score	[1, 2, 3, 1, 2, 3, 1]
결과	8

[2, 3, 2, 3]으로 상자 1개 → 2 × 4 = 8

---

문제 해석

사과가 m개 이상이면 가능한 만큼 계속 상자를 만들어 팔면 된다

문제는 어떻게 묶어야 이익이 최대가 되는가 인데
상자 가격이 최저 점수 × m 이니까, 최저 점수가 높을수록 좋은 상자가 된다

그래서 정렬한 뒤 뒤에서부터 m개씩 묶으면 자연스럽게 최저 점수가 큰 묶음들로 묶인다
나머지 사과들은 버리고 계산한다.

---

문제 풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int k, int m, vector<int> score) {
    int answer = 0;
    sort(score.begin(), score.end());

    for(int i = score.size() - m; i >= 0; i -= m)
    {
        answer += score[i] * m;
    }

    return answer;
}

---

핵심 포인트

1. 정렬 후 뒤에서부터 m개씩 묶기

오름차순으로 정렬하면 큰 값들이 뒤쪽에 몰리니까, 뒤에서부터 m개씩 묶어야 좋은 사과들이 한 상자에 들어간다

2. for문의 i가 각 상자의 최저 점수 위치

for(int i = score.size() - m; i >= 0; i -= m)

처음 i는 score.size() - m이다
이게 마지막 상자의 시작점이 된다

예를 들어 사과 12개에 m=3이면, 마지막 상자는 인덱스 9, 10, 11
이 중 인덱스 9가 그 상자의 최저값이라 i는 9에서 시작

3. m씩 건너뛰면서 누적

i -= m

한 상자가 끝나면 i를 m만큼 줄여서 그 다음 상자(앞쪽 묶음)의 최저값 위치로 간다
i가 0보다 작아지면 자연스럽게 종료되고, 앞쪽에 남는 자투리는 처리되지 않으니 버려지는 효과

---

동작 흐름 따라가보기

문제의 예시인 k = 4, m = 3, score = [4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]

이 내용을 예시로 따라가보자

 

정렬 후

[1, 1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4]
 0  1  2  3  4  5  6  7  8  9  10 11

총 12개

 

뒤에서부터 3개씩 묶기

[1, 1, 2] [2, 2, 2] [4, 4, 4] [4, 4, 4]
 버려짐    상자3     상자2     상자1

 

for문 흐름

항목 1회차 2회차 3회차 4회차 5회차

i 계산	12 - 3	9 - 3	6 - 3	3 - 3	0 - 3
i	9	6	3	0	-3
score[i]	4	4	2	1	종료
상자 구성	[4, 4, 4]	[4, 4, 4]	[2, 2, 2]	[1, 1, 2]	-
이익	12	12	6	3	-
answer	12	24	30	33	-

결과: 33