C++에서 두 요소가 인접하지 않도록 2 x n 그리드의 최대 합계

이 문제에서는 크기가 2 x n인 직사각형 그리드가 제공됩니다. 우리의 임무는 C++에서 두 요소가 인접하지 않도록 2 x n 그리드에서 최대 합을 찾는 프로그램을 만드는 것입니다.

문제 설명

최대 합을 찾기 위해 현재 요소에 인접한 요소를 세로, 가로 또는 대각선으로 선택할 수 없습니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력

rectGrid[2][] =389
411

출력

13

설명

가능한 모든 합계는

rectGrid[0][0] 즉 3에서 시작하면 9 또는 1만 추가할 수 있습니다. maxSum은 12입니다.

rectGrid[1][0] 즉 4에서 시작하면 9 또는 1만 추가할 수 있습니다. maxSum은 13입니다.

rectGrid[0][1] 즉 8에서 시작하면 요소를 추가할 수 없습니다. 최대 합계는 8입니다.

rectGrid[1][1] 즉 1에서 시작하면 요소를 추가할 수 없습니다. 최대 합계는 1입니다.

rectGrid[0][2] 즉 9에서 시작하면 3 또는 4만 추가할 수 있습니다. maxSum은 13입니다.

rectGrid[1][2] 즉 1에서 시작하면 3 또는 4만 추가할 수 있습니다. maxSum은 5입니다.

전체 최대 합계는 13입니다.

솔루션 접근 방식

문제는 우리가 지난 포스트에서 본 것처럼 인접한 두 요소가 없도록 최대 합과 유사합니다. 차이점은 여기에서 2D인 배열과 인접 요소에 대한 조건입니다. 따라서 행과 열 모두에 조건을 사용하여 최대 요소를 고려합니다. 각 열에는 두 개의 행이 있으므로 대체 요소를 최대한 고려합니다.

예시

솔루션의 작동을 설명하는 프로그램,

#include<iostream>
using namespace std;
int findMax(int a, int b){
   if(a > b)
      return a;
      return b;
   }
int calcMaxSum(int rectGrid[2][20], int N){
   int currectSum = 0;
   int nextSum = 0;
   int altSum;
   for (int i = 0; i<N; i++ ){
      altSum = findMax(nextSum, currectSum);
      currectSum = nextSum + findMax(rectGrid[0][i], rectGrid[1][i]);
      nextSum = altSum;
   }
   int maxSum = findMax(nextSum, currectSum);
   return maxSum;
}
int main(){
   int rectGrid[2][20] = {{3, 8, 9, 5},
   {4, 1, 2, 7}};
   int N = 4;
   cout<<"The maximum sum in a 2 x "<<N<<" grid such that no two elements are adjacent is "<<calcMaxSum(rectGrid, N);
   return 0;
}

출력

The maximum sum in a 2 x 4 grid such that no two elements are adjacent is 15