세 개의 양수 스택이 있다고 가정합니다. 우리는 허용되는 최상위 요소 제거와 함께 가능한 동일한 최대 스택 합계를 찾아야 합니다. 스택은 배열로 표시됩니다. 배열의 첫 번째 인덱스는 스택의 최상위 요소를 나타냅니다. 스택 요소가 [3, 10], [4, 5] 및 [2, 1]과 같다고 가정합니다. 출력은 0이 됩니다. 합계는 모든 스택에서 모든 요소를 제거한 후에만 동일할 수 있습니다.
이를 해결하기 위해 우리는 이 아이디어를 따를 것입니다. 아이디어는 각 스택의 합을 비교하는 것입니다. 동일하지 않은 경우 합이 최대인 스택의 맨 위 요소를 제거합니다. 우리는 다음 단계를 따를 것입니다 -
-
개별 스택에 있는 모든 요소의 합계를 찾습니다.
-
세 스택의 합계가 같으면 최대 합계입니다.
-
그렇지 않으면 3개의 스택 중 최대 합을 갖는 스택의 맨 위 요소를 제거합니다. 그런 다음 1단계와 2단계를 반복합니다.
예
#include <iostream>
#include <algorithm>
using namespace std;
int maxStackSum(int stk1[], int stk2[], int stk3[], int size1, int size2, int size3) {
int add1 = 0, add2 = 0, add3 = 0;
for (int i=0; i < size1; i++)
add1 += stk1[i];
for (int i=0; i < size2; i++)
add2 += stk2[i];
for (int i=0; i < size3; i++)
add3 += stk3[i];
int top1 =0, top2 = 0, top3 = 0;
int ans = 0;
while (true){
if (top1 == size1 || top2 == size2 || top3 == size3)
return 0;
if (add1 == add2 && add2 == add3)
return add1;
if (add1 >= add2 && add1 >= add3)
add1 -= stk1[top1++];
else if (add2 >= add3 && add2 >= add3)
add2 -= stk2[top2++];
else if (add3 >= add2 && add3 >= add1)
add3 -= stk3[top3++];
}
}
int main() {
int stack1[] = { 3, 2, 1, 1, 1 };
int stack2[] = { 4, 3, 2 };
int stack3[] = { 1, 1, 4, 1 };
int size1 = sizeof(stack1)/sizeof(stack1[0]);
int size2 = sizeof(stack2)/sizeof(stack2[0]);
int size3 = sizeof(stack3)/sizeof(stack3[0]);
cout << "The maximum sum is: " << maxStackSum(stack1, stack2, stack3, size1, size2, size3);
} 출력
The maximum sum is: 5