이 글에서는 임의의 대수식에서 최댓값을 찾는 C++ 프로그램을 소개합니다.
(x1 + x2 + x3 + … + xa) * (y1 + y2 + … + yb) 형태의 대수식과 총 (a + b)개의 정수가 주어졌을 때, 앞의 a개 숫자와 나머지 b개 숫자로 만들 수 있는 모든 조합을 고려하여 각 경우의 곱셈 값을 계산한 뒤, 그중 가장 큰 값을 도출하는 것이 목표입니다.
알고리즘
시작
함수 MaxValue() :
매개변수:
a[] = 요소들을 저장하는 배열
x, y = 정수
함수 본문:
1) 배열 요소들의 합을 구한다.
2) s = 0으로 초기화한다.
3) i = 0부터 (x + y - 1)까지 반복하면서 각 정수를 25만큼 더해 양수로 만든다.
4) i개의 숫자를 선택해 합 j를 만들 수 있으면 참(true)이 되는 불리언 배열 p[i][j]를 선언한다.
5) 배열을 초기화한다.
6) i = 0부터 (x + y) - 1까지 반복하며 p[i][j]가 참인지 확인한다.
즉, (x + y)개의 숫자 중 i개를 골라 합이 j가 되도록 할 수 있는지 판단한다.
7) max_value = -INF로 초기화한다.
8) i = 0부터 (MAX * MAX + 1) - 1까지 반복하며 n개의 숫자를 선택해
해당 합에 도달할 수 있는지 검사한다.
if (p[x][i])
배열의 음수 인덱스를 피하기 위해 숫자를 25만큼 이동시켰으므로,
실제 합을 다시 계산한다.
9) max_value를 출력한다.
끝예제 코드
#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define MAX 25
int MaxValue(int a[], int x, int y) {
int s = 0;
for (int i = 0; i < (x + y); i++) {
s += a[i];
a[i] += 25;
}
bool p[MAX+1][MAX * MAX + 1];
// 배열을 0으로 초기화한다.
memset(p, 0, sizeof(p));
p[0][0] = 1;
for (int i = 0; i < (x + y); i++) {
// 왼쪽 식에는 x개의 숫자가 사용되므로
// k는 최대 x까지만 가능하다.
for (int k = min(x, i + 1); k >= 1; k--) {
for (int j = 0; j < MAX * MAX + 1; j++) {
if (p[k - 1][j])
p[k][j + a[i]] = 1;
}
}
}
int max_value = -INF;
for (int i = 0; i < MAX * MAX + 1; i++) {
if (p[x][i]) {
int tmp = i - 25 * x;
max_value = max(max_value, tmp * (s - tmp));
}
}
cout << "Maximum Value: " << max_value ;
}
int main() {
int x = 2, y = 2; // x와 y 값을 입력받는다.
int ar[] = { 7,6,4,3 };
MaxValue(ar, x, y);
return 0;
}출력 결과
Maximum Value: 100
동작 원리 살펴보기
위 예제에서는 4개의 숫자 {7, 6, 4, 3}을 두 그룹씩 나누어 곱을 계산합니다. 가능한 조합은 다음과 같습니다.
(7 + 6) × (4 + 3) = 13 × 7 = 91
(7 + 4) × (6 + 3) = 11 × 9 = 99
(7 + 3) × (6 + 4) = 10 × 10 = 100
세 조합 중 가장 큰 값은 100이므로, 프로그램은 최종적으로 100을 출력합니다. 이처럼 음수 인덱스 문제를 피하기 위해 모든 수에 25를 더한 뒤 동적 계획법(DP)으로 도달 가능한 부분합을 추적하면, 모든 조합을 일일이 나열하지 않고도 효율적으로 최댓값을 구할 수 있습니다.