이 문제에서는 두 개의 배열 arr1[] 및 arr2[]와 두 개의 숫자N 및 M이 제공됩니다.
N은 arr1에서 가져온 요소의 수를 나타냅니다.
M은 arr2에서 가져온 요소의 수를 나타냅니다.
우리는 arr1[i]에서 arr2[i]까지의 요소 중 하나를 선택해야 하며, 이에 대한
합계를 최대화하지만 최대 N은 arr1에서, M은 arr2에서 가져올 수 있습니다.
우리의 임무는 C++에서 순서대로 두 개의 배열에서 요소를 선택하여 최대 합을 찾는 프로그램을 만드는 것입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
arr1[] = {5, 1, 6, 2, 8, 9} arr2[] = {8, 4, 7, 9, 1, 3} M = 3, N = 2
출력
28
설명
Here are the elements to be picked, i = 0, arr1[0] = 5, arr2[0] = 8.Element to be taken 8 i = 1, arr1[1] = 1, arr2[1] = 4.Element to be taken 4 i = 2, arr1[2] = 6, arr2[2] = 7.Element to be taken 6 i = 3, arr1[3] = 2, arr2[3] = 9.Element to be taken 2 i = 4, arr1[4] = 8, arr2[0] = 1.Element to be taken 8 maxSum = 8 + 4 + 6 + 2 + 8 = 28
해결 방법
문제를 해결하기 위해 각 솔루션은 요소 수가 M 또는 N에 도달할 때까지 arr1 및 arr2의 최대 요소를 찾는 것입니다. 그런 다음 모든 값을 더하여 합계를 찾습니다.
알고리즘
초기화 -
maxSum = 0
1단계 -
for i −> 0 to n
1.1단계 -
if arr1[i] > arr2[i] and M >= 0 −> maxSum += arr1[i].
1.2단계 -
else if arr1[i] < arr2[i] and N >= 0 −> maxSum += arr2[i].
1.3단계 -
else exit.
3단계 -
return maxSum
예
우리 솔루션의 작동을 설명하는 프로그램
#include<iostream> using namespace std; int calcMaxSumFromArrays(int arr1[], int arr2[], int N, int M, int size1, int size2) { int maxSum = 0; for(int i = 0; i < size1; i++){ if(arr1[i] > arr2[i] && N > 0){ maxSum += arr1[i]; N−−; } else if(arr1[i] <= arr2[i] && M > 0){ maxSum += arr2[i]; M−−; } else if(M > 0){ maxSum += arr2[i]; M−−; } else if(N > 0){ maxSum += arr1[i]; N−−; } else return maxSum; } return maxSum; } int main() { int arr1[]= {5, 1, 6, 2, 8, 9}; int arr2[]= {8, 4, 7, 9, 1, 3}; int N = 3, M = 2; int size1 = sizeof(arr1)/sizeof(arr1[0]); int size2 = sizeof(arr2)/sizeof(arr2[0]); cout<<"The maximum sum by picking elements from two arrays in order is "<<calcMaxSumFromArrays(arr1, arr2, N, M, size1, size2); return 0; }
출력
The maximum sum by picking elements from two arrays in order is 28