2차원 매트릭스가 주어지고, 각 셀 matrix[r, c]에는 그 위치에 놓인 코인의 개수가 저장되어 있다고 가정해 봅시다. 특정 셀 matrix[r, c]에서 코인을 가져가면, 바로 위 행(r - 1)과 아래 행(r + 1)의 모든 코인이 사라지며, 같은 행에 있는 좌우 이웃 셀인 matrix[r, c + 1]과 matrix[r, c - 1]의 코인 역시 함께 사라집니다. 이러한 규칙 속에서 우리가 수집할 수 있는 최대 코인 개수를 구하는 것이 목표입니다.
예를 들어 입력이 다음과 같다고 해 보겠습니다.
| 2 | 8 | 7 | 6 |
| 10 | 10 | 4 | 2 |
| 5 | 9 | 2 | 3 |
이 경우 출력은 26입니다. 코인이 8, 6, 9, 3개 들어 있는 셀들을 선택하면 어떤 셀도 서로를 없애지 않으며, 그 합이 정확히 26이 되기 때문입니다.
접근 방법
이 문제의 핵심은 잘 알려진 동적 계획법 패턴, 즉 '하우스 로버(House Robber)' 방식을 두 단계로 적용하는 것입니다.
- 행 내부 처리: 한 행 안에서 어떤 셀을 선택하면 좌우 인접 셀의 코인이 사라지므로, 결국 각 행에서 '인접하지 않은 원소들의 최대합'을 구하는 것과 같습니다.
- 행 간 처리: 어느 한 행을 선택하면 상하 인접 행 전체가 소멸하므로, 행별로 계산된 최대값들 사이에서도 다시 '인접하지 않은 값들의 최대합'을 구하면 됩니다.
구체적인 풀이 절차는 다음과 같습니다.
- 배열
arr을 인자로 받는 함수getmax()를 정의합니다. prev_max := 0,curr_max := 0,res := 0으로 초기화합니다.- 배열의 각 원소
num에 대해 다음을 반복합니다.temp := curr_maxcurr_max := num + prev_max— 현재 값을 선택했을 때 얻는 최대합prev_max := temp와 prev_max 중 큰 값— 직전 값을 건너뛰었을 때의 최대합res := res와 curr_max 중 큰 값
res를 반환합니다.- 메인 로직에서는 다음을 수행합니다.
- 매트릭스가 비어 있다면 0을 반환합니다.
m은 행의 개수,n은 열의 개수입니다.- 크기가
m인 배열row_sum을 0으로 초기화합니다. - i를 0부터 m - 1까지 순회하며
row_sum[i] := getmax(matrix[i])를 계산합니다. - 최종적으로
getmax(row_sum)을 반환합니다.
시간 복잡도
각 행마다 O(n)의 연산이 필요하고 행이 m개이므로 전체 시간 복잡도는 O(m × n), 공간 복잡도는 O(m)입니다.
예제 코드
아래 파이썬 구현을 통해 더 자세히 살펴 보겠습니다.
def getmax(arr):
prev_max, curr_max = 0, 0
res = 0
for num in arr:
temp = curr_max
curr_max = num + prev_max
prev_max = max(temp, prev_max)
res = max(res, curr_max)
return res
def solve(matrix):
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
row_sum = [0 for _ in range(m)]
for i in range(m):
row_sum[i] = getmax(matrix[i])
return getmax(row_sum)
matrix = [
[2, 8, 7, 6],
[10, 10, 4, 2],
[5, 9, 2, 3]
]
print(solve(matrix))입력
[ [2, 8, 7, 6], [10, 10, 4, 2], [5, 9, 2, 3] ]
출력
26
결과로 26이 출력되는 것을 확인할 수 있습니다. 첫 번째 행에서 8과 6(서로 인접하지 않음), 두 번째 행은 건너뛰고 세 번째 행에서 9와 3을 선택하는 조합이 최적해가 되기 때문입니다.