문제 개요
각 칸에 코인의 개수가 적혀 있는 2차원 행렬이 있다고 가정해 봅시다. 두 명의 친구가 이 행렬에서 코인을 수집하며, 시작 시점에 한 명은 왼쪽 위 모서리에, 다른 한 명은 오른쪽 위 모서리에 위치합니다. 두 수집가는 다음 규칙을 따라 움직입니다.
(i, j) 칸에 있는 수집가는 (i+1, j-1), (i+1, j), (i+1, j+1) 세 칸 중 하나로 이동할 수 있습니다.
어떤 칸에 도착하면 해당 칸의 모든 코인을 수집하며, 그 칸은 비게 됩니다.
수집가는 제자리에 머무를 수도 있지만, 각 칸의 코인은 단 한 번만 수집할 수 있습니다.
목표는 두 수집가가 모을 수 있는 최대 코인 수를 구하는 것입니다.
입력 예시
| 0 | 4 | 1 | 0 |
| 3 | 1 | 4 | 0 |
| 2 | 5 | 1 | 1 |
| 3 | 0 | 0 | 0 |
위 행렬이 입력으로 주어지면 출력은 17이 됩니다.
풀이 접근 방법: 동적 계획법
이 문제는 동적 계획법(Dynamic Programming)으로 해결할 수 있습니다. 핵심은 두 수집가가 항상 같은 행에 위치한다는 점입니다. 따라서 상태를 (행 r, 첫 번째 수집가의 열 c1, 두 번째 수집가의 열 c2)로 정의하면 됩니다.
풀이 과정은 다음과 같습니다.
A := 입력 행렬, R := 행의 개수, C := 열의 개수
dp(r, c1, c2) 함수를 정의합니다.
r이 R과 같으면 더 이상 내려갈 행이 없으므로 0을 반환합니다.
현재 행에서 얻을 수 있는 코인을 계산합니다. 두 수집가가 같은 칸(c1 == c2)에 있으면 코인을 한 번만 세고, 다르면 두 칸의 코인을 모두 더합니다. 즉, ans = base = A[r][c1] + (c1 != c2) * A[r][c2]
첫 번째 수집가의 다음 열 nc1을 [c1-1, c1, c1+1]에서, 두 번째 수집가의 다음 열 nc2를 [c2-1, c2, c2+1]에서 하나씩 시도합니다.
두 열이 모두 유효한 범위(0 이상 C 미만)라면 ans = max(ans, base + dp(r+1, nc1, nc2))로 갱신합니다.
ans를 반환합니다.
최종적으로 dp(0, 0, C-1)을 호출한 결과를 반환합니다.
파이썬 구현
class Solution:
def solve(self, A):
R, C = len(A), len(A[0])
def dp(r, c1, c2):
if r == R:
return 0
ans = base = A[r][c1] + (c1 != c2) * A[r][c2]
for nc1 in [c1 - 1, c1, c1 + 1]:
for nc2 in [c2 - 1, c2, c2 + 1]:
if 0 <= nc1 < C and 0 <= nc2 < C:
ans = max(ans, base + dp(r + 1, nc1, nc2))
return ans
return dp(0, 0, C - 1)
ob = Solution()
print(ob.solve([
[0, 4, 1, 0],
[3, 1, 4, 0],
[2, 5, 1, 1],
[3, 0, 0, 0]
]))입력
[
[0, 4, 1, 0],
[3, 1, 4, 0],
[2, 5, 1, 1],
[3, 0, 0, 0]
]출력
17성능 최적화 팁
위 구현은 동일한 상태를 반복해서 계산할 수 있으므로, 입력 크기가 커지면 실행 시간이 급격히 늘어날 수 있습니다. functools.lru_cache 데코레이터를 dp 함수에 적용해 메모이제이션을 추가하면, 각 상태를 한 번씩만 계산하게 되어 시간 복잡도를 O(R × C² × 9) 수준으로 크게 줄일 수 있습니다. 실전 코딩 테스트나 대규모 입력에서는 메모이제이션을 반드시 활용하는 것이 좋습니다.