Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 2×n 그리드 최대 합 알고리즘: 인접한 두 요소를 선택하지 않는 방법

이 문제에서는 크기가 2×n인 직사각형 그리드가 주어지며, 어떤 두 요소도 서로 인접하지 않도록 요소를 선택하면서 얻을 수 있는 최대 합을 구하는 C++ 프로그램을 작성해야 합니다.

문제 설명

최대 합을 구하려면 현재 선택한 요소와 세로, 가로, 대각선 어느 방향으로든 인접한 요소는 함께 선택할 수 없습니다.

예시를 통해 문제를 자세히 살펴보겠습니다.

입력

rectGrid[2][] = { {3, 8, 9},
                  {4, 1, 1} }

출력

13

설명

시작 위치별로 가능한 모든 합을 계산하면 다음과 같습니다.

  • rectGrid[0][0] = 3에서 시작 → 9 또는 1만 추가 가능 → 최대 합 12
  • rectGrid[1][0] = 4에서 시작 → 9 또는 1만 추가 가능 → 최대 합 13
  • rectGrid[0][1] = 8에서 시작 → 추가 가능한 요소 없음 → 최대 합 8
  • rectGrid[1][1] = 1에서 시작 → 추가 가능한 요소 없음 → 최대 합 1
  • rectGrid[0][2] = 9에서 시작 → 3 또는 4만 추가 가능 → 최대 합 13
  • rectGrid[1][2] = 1에서 시작 → 3 또는 4만 추가 가능 → 최대 합 5

따라서 전체 최대 합은 13입니다.

해결 접근 방법

이 문제는 앞서 다룬 "두 요소가 인접하지 않도록 선택하는 최대 합" 문제와 매우 유사합니다. 다만 배열이 2차원이라는 점과 인접 판정 조건이 다르다는 점이 차이입니다.

핵심 아이디어는 다음과 같습니다. 각 열에는 두 개의 값이 있으므로, 특정 열을 선택하기로 했다면 그 열에서는 두 값 중 더 큰 값을 선택하는 것이 항상 유리합니다. 또한 인접한 열은 선택할 수 없으므로, 결국 이 문제는 "하나 건너뛰면서 열을 선택하는 최대 합" 문제로 환원됩니다. 이는 동적 계획법(DP)으로 O(N) 시간 안에 해결할 수 있습니다.

알고리즘 동작 원리

  • currectSum: 직전 열을 건너뛰고, 현재 열에서 더 큰 값을 선택했을 때의 누적 최대 합
  • nextSum: 현재 열을 선택하지 않고 건너뛸 때의 누적 최대 합
  • altSum: 다음 반복에 전달할, 현재까지의 전체 최대 합

매 열마다 altSum = max(nextSum, currectSum)으로 지금까지의 최댓값을 저장하고, currectSum에는 "직전 열을 건너뛴 합 + 현재 열의 최댓값"을, nextSum에는 altSum을 대입합니다. 마지막에 두 값 중 큰 값이 정답이 됩니다.

예제 코드

아래 프로그램은 위 해결 방법의 동작을 보여줍니다.

#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

복잡도 분석

  • 시간 복잡도: O(N) — 각 열을 한 번씩만 순회합니다.
  • 공간 복잡도: O(1) — 상수 개수의 변수만 사용합니다.

마무리

2×n 그리드에서 인접하지 않은 요소의 최대 합 문제는 1차원 배열의 "인접하지 않은 최대 합" 문제를 2차원으로 확장한 형태입니다. 각 열에서 두 값 중 최댓값을 취하면 1차원 문제와 동일해진다는 점을 활용하면, 간단한 동적 계획법으로 효율적으로 해결할 수 있습니다.