문제

• 
• 시간 제한: 1초
• 메모리 제한: 512MB

Problem Analysis

현재 위치가 (r, c)일 때, 이전의 위치는 좌, 우, 그리고 위가 가능하다. 이렇게 (N, M)에서부터 (1,1)로 recursive 하게 내려가면서 모든 경우를 조사하여 풀 수 있는데, sub-problems이 반복된다. 따라서, Dynamic Programming으로 풀 수 있다.

Algorithm

Bottom-Up 방식으로 개선하여, (1, 1)에서부터 (N, M)으로 iterative 하게 dp를 작성한다.
이때, 이미 탐사한 지역을 방문하면 안 되기 때문에, (r, c)에서의 값을 아래와 같이 구분하여 구한다.

• from_left: (r, c-1)의 FL 또는 FU 경로와 조합하여 가능한 최대
• from_right: (r, c+1)의 FR 또는 FU 경로와 조합하여 가능한 최대
• from_up: (r-1, c)의 max와 조합
• max: FL, FR, FU 중에서 택

Data Structure

• dp_data: 위의 FL, FR, FU, max 값을 담는 struct
• dp_data DP[N][M]: dp 값 저장

결과

Other

시간 복잡도는 O(NM)이다.