C++로 구현하는 자동차 판매 최대 수익 계산 프로그램

한 자동차 회사가 빨간색 차 p대와 파란색 차 q대를 서로 다른 가격으로 판매하기로 결정했다고 가정해 보겠습니다. 현재 회사 재고에는 빨간색 차 a대, 파란색 차 b대, 그리고 아직 도색되지 않은 무색(미도색) 차 c대가 보관되어 있으며, 각 차량의 가치는 배열 A, B, C에 담겨 주어집니다.

회사는 하루 동안 반드시 p + q대의 차량을 판매해야 하며, 이때 가능한 한 최대 이익을 실현해야 합니다. 무색 차량은 빨간색 또는 파란색 중 원하는 색으로 자유롭게 도색할 수 있습니다. 이 조건에서 판매를 통해 얻을 수 있는 최대 수익을 구하는 것이 이 문제의 목표입니다.

입력 예시와 결과

예를 들어 입력이 p = 3, q = 3, a = 3, b = 3, c = 2, A = {150000, 200000, 200000}, B = {150000, 120000, 180000}, C = {210000, 160000, 150000}라고 해보겠습니다. 이 경우 출력은 1100000입니다.

무도색 차량 2대를 각각 원하는 색으로 도색해 판매하면, 기존 차량 중 가장 저렴한 두 대를 제외한 고가 차량(200000, 200000, 180000, 150000)과 함께 도색 차량(210000, 160000)을 판매하게 됩니다. 이때 총 수익은 200000 + 200000 + 180000 + 150000 + 210000 + 160000 = 1100000입니다. 반면 도색 없이 기존 차량만 판매하면 200000 + 200000 + 180000 + 150000 + 150000 + 120000 = 1000000에 그치므로, 무도색 차량을 활용하는 전략이 훨씬 유리함을 알 수 있습니다.

알고리즘 접근 방법

이 문제는 그리디 방식과 누적 합(prefix sum)을 활용해 다음 단계로 해결할 수 있습니다.

배열 dp 정의
배열 A, B, C를 내림차순 정렬
i := 0부터 i < p까지 반복하며 dp 끝에 A[i] 삽입
i := 0부터 i < q까지 반복하며 dp 끝에 B[i] 삽입
배열 dp를 정렬한 뒤 첫 번째 요소를 제외하고 역순으로 배치
i := 1부터 dp 크기까지 반복하며 dp[i] := dp[i] + dp[i - 1] (누적 합 계산)
tmp := 0
res := dp의 마지막 요소
i := 1부터 min(c, p + q)까지 반복하며:
   tmp := tmp + C[i - 1]
   res := res와 (dp[p + q - i] + tmp) 중 최댓값 선택
res 반환

핵심 아이디어는 다음과 같습니다. 먼저 빨간색 차와 파란색 차의 가치를 모두 모아 내림차순으로 정렬하면, 도색 없이 판매할 때 가장 좋은 조합을 손쉽게 얻을 수 있습니다. 이후 무도색 차량을 1대씩 추가로 도색 판매하는 경우를 시뮬레이션하면서, 기존 차량 중 가장 낮은 가치의 차량을 도색 차량으로 교체했을 때 수익이 증가하는지 확인하고, 그중 최댓값을 정답으로 반환합니다.

구현 예시

아래의 C++ 구현 예시를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

int solve(int p, int q, int a, int b, int c, vector<int> A, vector<int> B, vector<int> C){
   vector<int> dp(1, 0);
   sort(A.rbegin(), A.rend());
   sort(B.rbegin(), B.rend());
   sort(C.rbegin(), C.rend());
   for(int i = 0; i < p; ++i)
      dp.push_back(A[i]);
   for(int i = 0; i < q; ++i)
      dp.push_back(B[i]);
   sort(dp.begin(), dp.end());
   reverse(dp.begin() + 1, dp.end());
   for(int i = 1; i < (int)dp.size(); ++i)
      dp[i] += dp[i - 1];
   int tmp = 0;
   int res = dp.back();
   for(int i = 1; i <= min(c, p + q); ++i) {
      tmp += C[i - 1];
      res = max(res, dp[p + q - i] + tmp);
   }
   return res;
}
int main() {
   int p = 3, q = 3, a = 3, b = 3, c = 2;
   vector<int> A = {150000, 200000, 200000}, B = {150000, 120000, 180000}, C = {210000, 160000, 150000};
   cout<< solve(p, q, a, b, c, A, B, C);
   return 0;
}

입력

3, 3, 3, 3, 2, {150000, 200000, 200000}, {150000, 120000, 180000}, {210000, 160000, 150000}