문제 개요
각 칸에 동전이 저장되어 있는 2차원 행렬(격자)이 있다고 가정해 보겠습니다. [0,0] 위치에서 출발하여 오른쪽 또는 아래로만 이동할 수 있을 때, 오른쪽 아래 모서리에 도달하기까지 수집할 수 있는 최대 동전 수를 구하는 것이 목표입니다.
입력 예시
| 1 | 4 | 2 | 2 |
| 0 | 0 | 0 | 5 |
위 입력에 대한 출력은 14입니다. 경로 [1, 4, 2, 2, 5]를 따라 이동하면 각 칸의 동전을 모두 더해 최댓값을 얻을 수 있습니다.
풀이 접근 방식: 동적 계획법(DP)
이 문제는 각 칸에 도달했을 때의 최대 누적 동전 수를 저장하는 방식으로 효율적으로 해결할 수 있습니다. 원본 행렬을 그대로 활용해 제자리(in-place) 갱신하면 추가 메모리 없이 풀이할 수 있습니다.
첫 번째 열 처리: r을 1부터 행 개수까지 순회하며
A[r][0] += A[r-1][0]로 위쪽 값을 누적합니다.첫 번째 행 처리: c를 1부터 열 개수까지 순회하며
A[0][c] += A[0][c-1]로 왼쪽 값을 누적합니다.나머지 셀 처리: r과 c를 1부터 각각 행·열 크기까지 순회하며, 현재 칸의 동전에 위쪽 칸과 왼쪽 칸 중 더 큰 값을 더합니다.
A[r][c] += max(A[r-1][c], A[r][c-1])결과 반환: 모든 갱신이 끝난 후 행렬의 오른쪽 아래 값이 곧 최대 동전 수입니다.
핵심 아이디어는 특정 칸에 도달할 수 있는 경로는 반드시 바로 위 또는 바로 왼쪽 칸을 거친다는 점입니다. 따라서 두 경로 중 동전 합이 큰 쪽을 선택하면 전체 최적해를 보장할 수 있습니다.
구현 예제
아래 파이썬 코드로 위 알고리즘을 확인해 보겠습니다.
class Solution:
def solve(self, A):
# 첫 번째 열 누적
for r in range(1, len(A)):
A[r][0] += A[r-1][0]
# 첫 번째 행 누적
for c in range(1, len(A[0])):
A[0][c] += A[0][c-1]
# 나머지 셀: 위쪽/왼쪽 중 큰 값 선택
for r in range(1, len(A)):
for c in range(1, len(A[0])):
A[r][c] += max(A[r-1][c], A[r][c-1])
return A[-1][-1]
ob = Solution()
matrix = [
[1, 4, 2, 2],
[0, 0, 0, 5]
]
print(ob.solve(matrix))입력
matrix = [
[1, 4, 2, 2],
[0, 0, 0, 5]
]출력
14
복잡도 분석
시간 복잡도: O(m × n) — 행렬의 모든 칸을 한 번씩만 방문합니다.
공간 복잡도: O(1) — 입력 행렬을 제자리에서 갱신하므로 추가 공간이 필요하지 않습니다.