이 문제의 목표는 최대 M개의 제품을 판매하여 얻을 수 있는 최대 수익을 계산하는 것입니다.
전체 제품의 개수는 N개이며, 각 제품의 원가(Cost Price)와 판매가(Selling Price)는 각각 CP[]와 SP[] 배열에 주어집니다.
입력 예시 1
N=6, M=4
CP[]={1,9,5,8,2,11}
SP[]={1,15,10,16,5,20}출력:
28
설명: 각 제품을 판매했을 때 얻는 수익은 순서대로 0, 6, 5, 8, 3, 9입니다.
따라서 단 4개의 제품만 판매하여 최대 수익을 내려면 수익이 가장 높은 제품, 즉 2번, 3번, 4번, 6번 제품을 선택해야 합니다.
최대 수익 = 6 + 5 + 8 + 9 = 28
입력 예시 2
N=3, M=2
CP[]={10,20,30}
SP[]={19,22,38}출력:
17
해결 접근 방법
- 각 제품에서 얻는 수익을 저장하기 위해 크기가 N인 int형 배열 Profit[]를 생성합니다.
- 최종 최대 수익을 저장할 int형 변수 Total을 선언합니다.
- i=0부터 i<N까지 반복문을 실행합니다.
- 반복문 안에서 Profit[i] = Sp[i] - Cp[i]를 계산하여 각 제품의 수익을 구합니다.
- sort(Profit, Profit + N, greater<int>()) 함수를 호출하여 Profit[] 배열을 내림차순으로 정렬합니다.
- 다시 i=0부터 i<M까지 반복문을 실행합니다.
- 반복문 안에서 if(Profit[i]>0) 조건으로 해당 값이 양수인지 확인하고, 양수라면 total += Profit[i]로 누적합니다.
- 최종적으로 total 값을 반환합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
// 수익을 계산하는 함수
int MaxProfit(int N, int M, int Cp[], int Sp[]){
int Profit[N];
int total = 0;
// 각 제품의 수익 계산
for (int i = 0; i < N; i++)
Profit[i] = Sp[i] - Cp[i];
// 수익 배열을 내림차순으로 정렬
sort(Profit, Profit + N, greater<int>());
// 가장 좋은 M개의 수익 더하기
for (int i = 0; i < M; i++){
if (Profit[i] > 0)
total += Profit[i];
else
break;
}
return total;
}
// 메인 함수
int main(){
int MP;
int N=6,M=4;
int CP[] = { 1, 9, 5, 8, 2, 11 };
int SP[] = { 1, 15, 10, 16, 5, 20 };
MP = MaxProfit(N, M, CP, SP);
cout<<"Maximum Profit:"<<MP;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Maximum Profit: 28
핵심 정리
이 알고리즘의 시간 복잡도는 정렬 과정 때문에 O(N log N)이며, 공간 복잡도는 O(N)입니다. 핵심 아이디어는 모든 제품의 수익을 먼저 계산한 뒤, 수익이 높은 순서대로 정렬하여 상위 M개 중 양수인 수익만 선택적으로 더하는 것입니다. 손실이 발생하는 제품(수익이 음수인 경우)은 판매하지 않는 것이 전체 수익 극대화에 유리하기 때문에, break 문으로 반복을 종료하여 불필요한 연산을 줄일 수 있습니다.