📖 문제 탐색

문제

• 로봇이 왼쪽 위 (1,1)에서 오른쪽 아래 ($N$, $M$)까지 이동하며 자원을 탐색한다.
• 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있다. 자신이 위치한 ($x$, $y$)에 자원이 있는 경우에만 해당 자원을 채취할 수 있다.
• 탐사 영역에 대한 정보가 주어지면, 로봇이 탐색할 수 있는 자원의 최대 숫자를 구해야 한다.
• 탐사할 영역의 세로 길이 $N$, 가로 길이 $M$ (1 ≤ $N$, $M$ ≤ 300)

시간복잡도

• 1≤ $N$, $M$ ≤ 300이므로, 2차원 배열을 활용해도 $O(NM)$ = $O($90,000) 연산으로 해결이 가능하다.

알고리즘

• DP를 이용하면 빠르게 해결할 수 있다.
• 그리디나 BFS/DFS로는 접근하기 어렵다. 최적해를 구하기 위한 누적 합을 관리하는 방식이 적절하다.

🔎 문제 접근

1. DP 테이블을 정의한다.
   • dp[i][j]: (i, j)까지 도달했을 때 최대 자원 개수