내리막길
면접 대비시간 제한2초메모리 제한128 MB
격자에서 상하좌우로만 이동하며 높이가 항상 감소해야 할 때, 좌상단에서 우하단까지 가는 경로 수를 메모이제이션 DFS로 계산합니다.
문제
세준이는 여행 중 직사각형 지도를 얻었다. 지도는 여러 칸으로 나뉘어 있으며, 각 칸은 하나의 지점을 나타낸다. 각 칸에는 그 지점의 높이가 적혀 있고, 이동은 상하좌우로 맞닿은 칸 사이에서만 할 수 있다.
세준이는 왼쪽 위 칸에서 출발해 오른쪽 아래 칸까지 가려고 한다. 힘을 덜 들이기 위해, 매번 현재 칸보다 높이가 낮은 칸으로만 이동한다. 위 지도에서는 다음 세 가지 경로가 가능하다.
지도가 주어질 때, 왼쪽 위 칸에서 오른쪽 아래 칸까지 항상 더 낮은 칸으로만 이동하는 경로의 수를 구하라.
입력
첫째 줄에 지도의 세로 크기 M과 가로 크기 N이 공백으로 구분되어 주어진다. 다음 M개 줄에는 각 줄마다 N개의 자연수가 주어지며, 위쪽 행부터 차례대로 각 지점의 높이를 나타낸다.
M과 N은 각각 500 이하의 자연수이고, 각 지점의 높이는 10,000 이하의 자연수이다.
출력
첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에서 H는 1,000,000,000 이하의 음이 아닌 정수이다.