백준 1520 c++

탐색문제로 탐색을 현위치의 값보다 작은 위치를 값으로 탐색가능하다 => 이것을 통해 기존의 탐색에서는 visited[] 배열을 탐색의 중복을 피할 수 있었는데 이번에는 작은 위치 값만 이동할 수 있어서 다음 위치를 방문했는 지 안했는 지를 생각할 필요가 없다.

문제풀이 

DFS() - 시작위치에서(0,0) 너비 우선 탐색으로 마지막 위치에 도달하면 count를 증가하는 형식으로 풀었는데 답은 맞는데 시간 초과가 발생함

시간 초과를 줄이기 위해 메모이제이션을 사용.

현재위치에서 도착위치까지 가는 방법은  현재의 위치갈 수 있는 다음위치들의 도착지까지 가는 방법을 다 더하는 식으로 메모이제이션을 사용함.

 

기존의 좌표 탐색문제에서 메모이제이션을 추가한 문제

 

https://www.acmicpc.net/problem/1520

1520번: 내리막 길