각 칸에 포인트가 배치된 행렬(그리드)이 주어졌을 때, 두 번의 순회(traversal)를 통해 얻을 수 있는 최대 포인트를 구하는 방법을 알아보겠습니다.
문제 조건
이 문제를 해결하려면 다음 세 가지 조건을 만족해야 합니다.
- 첫 번째 순회는 그리드의 왼쪽 위 칸에서 시작하여 왼쪽 아래 모서리로 이동하고, 두 번째 순회는 오른쪽 위 모서리에서 시작하여 오른쪽 아래 모서리로 이동합니다.
- 한 칸에서 다음 칸으로 이동할 때는 현재 칸 기준으로 아래, 왼쪽 아래 대각선, 오른쪽 아래 대각선 방향만 가능합니다.
- 첫 번째 순회에서 이미 포인트를 획득한 칸은 두 번째 순회에서 다시 포인트를 얻을 수 없습니다. 즉, 같은 칸의 점수는 한 번만 계산됩니다.
입력과 출력
입력: 포인트가 담긴 그리드 3 6 8 2 5 2 4 3 1 1 20 10 1 1 20 10 1 1 20 10 출력: 두 번의 순회로 수집한 최대 포인트는 73입니다. 첫 번째 순회에서 획득: 3 + 2 + 20 + 1 + 1 = 27 두 번째 순회에서 획득: 2 + 4 + 10 + 20 + 10 = 46
알고리즘
이 문제는 메모이제이션(memoization)을 활용한 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 두 순회를 각각 따로 계산하는 대신, 같은 행(x)에 있는 두 순회의 열 위치(y1, y2)를 상태로 묶어 처리합니다.
findMaxVal(mTable, x, y1, y2)
입력 − 메모이제이션용 3차원 배열(mTable), x 값, y1과 y2
출력 − 해당 상태에서 얻을 수 있는 최댓값
Begin
if x, y1, y2가 유효하지 않으면
return -∞
if 두 순회가 모두 완료되었으면
if y1 = y2이면
return grid[x, y1]
else
return grid[x, y1] + grid[x, y2]
if 두 순회가 마지막 행에 있지만 완료되지 않았으면
return -∞
if 이미 해결된 부분 문제라면
return mTable[x, y1, y2]
res := -∞
if y1 = y2이면
temp := grid[x, y1]
else
temp := grid[x, y1] + grid[x, y2]
// 두 순회의 가능한 모든 이동 조합에 대해 재귀 호출 후 최댓값 갱신
res := max(res, temp + findMaxVal(mTable, x+1, y1, y2-1))
res := max(res, temp + findMaxVal(mTable, x+1, y1, y2+1))
res := max(res, temp + findMaxVal(mTable, x+1, y1, y2))
res := max(res, temp + findMaxVal(mTable, x+1, y1-1, y2))
res := max(res, temp + findMaxVal(mTable, x+1, y1-1, y2-1))
res := max(res, temp + findMaxVal(mTable, x+1, y1-1, y2+1))
res := max(res, temp + findMaxVal(mTable, x+1, y1+1, y2))
res := max(res, temp + findMaxVal(mTable, x+1, y1+1, y2-1))
res := max(res, temp + findMaxVal(mTable, x+1, y1+1, y2+1))
return mTable[x, y1, y2] = res
EndC++ 구현 예제
#include<iostream>
#define ROW 5
#define COL 4
using namespace std;
int grid[ROW][COL] = {
{3, 6, 8, 2},
{5, 2, 4, 3},
{1, 1, 20, 10},
{1, 1, 20, 10},
{1, 1, 20, 10},
};
bool isValidInput(int x, int y1, int y2) {
return (x >= 0 && x < ROW && y1 >=0 && y1 < COL && y2 >=0 && y2 < COL);
}
int max(int a, int b) {
return (a>b)?a:b;
}
int findMaxVal(int mTable[ROW][COL][COL], int x, int y1, int y2) {
if (!isValidInput(x, y1, y2)) // 유효하지 않은 칸이면 음의 무한대 반환
return INT_MIN;
if (x == ROW-1 && y1 == 0 && y2 == COL-1) // 두 순회가 모두 완료된 경우
return (y1 == y2)? grid[x][y1]: grid[x][y1] + grid[x][y2];
if (x == ROW-1) // 마지막 행에 있지만 아직 완료되지 않은 경우
return INT_MIN;
if (mTable[x][y1][y2] != -1) // 이미 해결된 부분 문제인 경우
return mTable[x][y1][y2];
int answer = INT_MIN; // 초기값은 음의 무한대
int temp = (y1 == y2)? grid[x][y1]: grid[x][y1] + grid[x][y2]; // 현재 칸에서의 획득 점수
// 가능한 모든 이동 조합을 탐색하며 최댓값 계산
answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2-1));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2+1));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2-1));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2+1));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2-1));
answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2+1));
return (mTable[x][y1][y2] = answer); // 결과를 mTable에 저장하고 반환
}
int findMaxCollection() {
// 메모이제이션 테이블 생성 및 모든 값을 -1로 초기화
int mTable[ROW][COL][COL];
for(int i = 0; i<ROW; i++)
for(int j = 0; j<COL; j++)
for(int k = 0; k<COL; k++)
mTable[i][j][k] = -1;
return findMaxVal(mTable, 0, 0, COL-1);
}
int main() {
cout << "Maximum collection is " << findMaxCollection();
return 0;
}실행 결과
Maximum collection is 73
정리
이 문제의 핵심은 두 순회를 독립적으로 계산하지 않고, 같은 행에서 두 순회의 위치 쌍 (y1, y2)을 하나의 상태로 정의하는 것입니다. 이렇게 하면 시간 복잡도는 O(ROW × COL × COL)가 되며, 겹치는 부분 문제를 메모이제이션으로 저장해 중복 계산을 제거할 수 있습니다. 또한 두 순회가 같은 칸(y1 = y2)에 도달했을 때는 점수를 한 번만 더하도록 처리하는 것이 중요합니다.