BOJ - 11048 ) 이동하기

 

 

준규는 1,1 에서 출발하여 주어진 N,M 까지 이동하며 이동하는 칸의 사탕을 가져간다. N,M 칸에 도달할 때 준규가 가질수 있는 최대의 사탕 개수를 도출하는 문제이다. 해당 문제의 접근법은 다음과 같다.

 

 

1. 이동하는 방법은 오른쪽, 아래, 오른쪽 대각선으로 정해져 있다.

2. 준규가 이동할 수 있는 미로 칸마다 사탕을 가져올 수 있는 최대값을 갱신하며 진행한다.

3. 최대값을 갱신할 때, 위 칸에서 내려오는 경우, 대각선 칸에서 내려오는 경우, 왼쪽 칸에서 오는 경우를 비교한다.