문제 상황
어떤 제조업체가 특정 제품에 들어갈 부품을 전문적으로 생산한다고 가정해 봅시다. 이 제조업체는 n가지 서로 다른 종류의 부품을 보유하고 있으며, 각 부품은 세 가지 기준(A, B, C)에 따라 평점이 매겨집니다. n개 부품의 평점은 배열 ratings에 담겨 있고, 각 원소는 (A, B, C) 형태입니다.
이제 어느 OEM 업체가 자사 제품 하나당 m개의 부품을 이 제조업체로부터 구매하려고 합니다. 단, 부품을 선택할 때 아래 두 가지 조건을 만족해야 합니다.
동일한 부품을 두 개 이상 구매할 수 없습니다.
다음 식의 값 V가 최대가 되도록 부품 조합을 선택합니다.
V = |A 기준 총평점| + |B 기준 총평점| + |C 기준 총평점|
즉, OEM이 선택할 수 있는 부품 조합 중에서 V의 최댓값을 구하는 것이 우리의 목표입니다.
예시
입력이 n = 6, m = 4, ratings = {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3, 6}}이라면 출력은 56이 됩니다.
OEM이 1, 3, 5, 6번 부품을 선택했다면 각 카테고리별 총평점은 다음과 같습니다.
Category A = 2 + 4 + 7 + 4 = 17
Category B = 3 + 8 + 2 + 3 = 16
Category C = 5 + 5 + 7 + 6 = 23
따라서 V의 총합은 17 + 16 + 23 = 56 입니다.
풀이 접근 방법
핵심 아이디어는 각 부품마다 A, B, C 세 값의 부호 조합(±) 8가지 경우를 모두 미리 계산해 두는 것입니다. 절댓값의 합은 결국 '부호를 잘 골랐을 때의 부호 있는 합'의 최댓값과 같기 때문에, 8가지 부호 조합 중 어떤 조합이든 상위 m개 부품의 합이 가장 커지는 경우가 곧 정답이 됩니다.
구체적인 절차는 다음과 같습니다.
각 부품 i에 대해 a+b+c, a−b−c, a+b−c, a−b+c, −a+b+c, −a−b−c, −a+b−c, −a−b+c 의 8가지 값을 배열 arr에 저장합니다.
8개의 배열 각각을 내림차순으로 정렬합니다.
m이 0이면 V는 0입니다.
그렇지 않으면 각 부호 조합 j에 대해 상위 m개 값의 합 k를 구하고, 그중 최댓값을 V로 반환합니다.
N := 100
크기가 9 x N인 배열 arr 선언
배열 ans 선언
for initialize i := 0, when i < n, update (increase i by 1), do:
a := ratings[i]의 첫 번째 값
b := ratings[i]의 두 번째 값
c := ratings[i]의 세 번째 값
arr[1, i] := a + b + c
arr[2, i] := a - b - c
arr[3, i] := a + b - c
arr[4, i] := a - b + c
arr[5, i] := -a + b + c
arr[6, i] := -a - b - c
arr[7, i] := -a + b - c
arr[8, i] := -a - b + c
for initialize i := 1, when i <= 8, update (increase i by 1), do:
배열 arr[i] 정렬
for initialize i := 1, when i <= 8, update (increase i by 1), do:
배열 arr[i]를 뒤집어 내림차순으로 만듦
m이 0과 같으면:
V := 0
그렇지 않으면:
for initialize j := 1, when j <= 8, update (increase j by 1), do:
k := 0
for initialize i := 0, when i < m, update (increase i by 1), do:
k := k + arr[j, i]
V := V와 k 중 최댓값
return V
예제 코드
아래 구현을 통해 더 잘 이해해 봅시다.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int modval = (int) 1e9 + 7;
#define N 100
int solve(int n, int m, vector<tuple<int, int, int>> ratings) {
int V, arr[9][N];
vector<int> ans;
for(int i = 0 ; i < n ; i++) {
int a, b, c;
tie(a, b, c) = ratings[i];
arr[1][i] = a + b + c;
arr[2][i] = a - b - c;
arr[3][i] = a + b - c;
arr[4][i] = a - b + c;
arr[5][i] = -a + b + c;
arr[6][i] = -a - b - c;
arr[7][i] = -a + b - c;
arr[8][i] = -a - b + c;
}
for(int i = 1 ; i <= 8 ; i++)
sort(arr[i], arr[i] + n);
for(int i = 1 ; i <= 8 ; i++)
reverse(arr[i], arr[i] + n);
if (m == 0)
V = 0;
else {
for (int j = 1; j <= 8; j++) {
int k = 0;
for (int i = 0; i < m; i++)
k += arr[j][i];
V = max(V, k);
}
}
return V;
}
int main() {
int n = 6, m = 4;
vector<tuple<int, int, int>> ratings = {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3, 6}};
cout << solve(n, m, ratings);
return 0;
}
입력
6, 4, {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3, 6}}출력
56