C++를 사용하여 대수식의 최솟값을 찾는 프로그램을 소개합니다. (x1 + x2 + x3 + … + xa) × (y1 + y2 + … + yb) 형태의 대수식과 (a + b)개의 정수가 주어졌을 때, a개의 숫자와 나머지 b개의 숫자로 만들 수 있는 모든 조합을 고려해 값을 계산한 뒤, 그중 가장 작은 값을 도출하는 것이 목표입니다.
알고리즘
Begin
function MinValue() :
Arguments:
a[] = 요소들을 저장하는 배열
x, y = 정수
Body of the function:
1) 배열 요소들의 총합을 구합니다.
2) s = 0으로 초기화합니다.
3) i = 0부터 (x + y) - 1까지 반복하며 각 정수에 25를 더해 양수로 변환합니다.
4) 부울 배열 p[i][j]를 선언합니다. i개의 숫자를 선택해 합 j를 만들 수 있으면 true입니다.
5) 배열을 초기화합니다.
6) i = 0부터 (x + y) - 1까지 반복하며 p[i][j]가 true인지 확인합니다. true라면 (x + y)개의 숫자 중 i개를 골라 합 j를 만드는 것이 가능하다는 의미입니다.
7) min_value = INF로 초기화합니다.
8) i = 0부터 (MAX * MAX + 1) - 1까지 반복하며 x개의 숫자를 선택해 해당 합에 도달할 수 있는지 검사합니다.
if (p[x][i])
숫자들을 25만큼 이동시켰으므로 실제 합을 다시 계산합니다(배열의 음수 인덱스 방지).
9) min_value를 출력합니다.
End
예제 코드
#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define MAX 25
int MinValue(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];
//Initialize the array to 01.
memset(p, 0, sizeof(p));
p[0][0] = 1;
for (int i = 0; i < (x + y); i++) {
// k can be at max x because the
// left expression has x numbers
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 min_value = INF;
for (int i = 0; i < MAX * MAX + 1; i++) {
if (p[x][i]) {
int tmp = i - 25 * x;
min_value = min(min_value, tmp * (s - tmp));
}
}
cout << "Minimum Value: " << min_value ;
}
int main() {
int x = 2, y = 2; //input is taken of x and y.
int ar[] = { 7,6,4,3 };
MinValue(ar, x, y);
return 0;
}
출력 결과
Minimum Value: 91
코드 동작 원리
이 코드의 핵심은 동적 계획법(DP)입니다. 음수 인덱스 접근을 방지하기 위해 모든 입력 값에 25를 더하고, 2차원 부울 배열 p[i][j]를 통해 "i개의 숫자를 선택했을 때 합 j를 만들 수 있는가"를 추적합니다. 마지막으로 x개의 숫자로 만들 수 있는 모든 합에 대해, 전체 합에서 그 값을 뺀 나머지 숫자들의 합을 곱한 결과를 비교하여 최솟값을 구합니다.
예를 들어 x = 2, y = 2이고 배열이 {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
세 경우 중 가장 작은 값인 91이 최종 결과로 출력됩니다.