internet record

[백준] - 1520 내리막 길

[백준] - 1520 내리막 길 문제에 대한 글입니다. 문제 링크 : https://www.acmicpc.net/problem/1520문제 접근격자점에서 시작합니다. 격자점 현재 위치의 값보다 작은 값으로만 이동할 수 있는 제약 조건이 있습니다.이러한 조건을 고려하여 (0,0)에서 (n-1, m-1)까지 갈 수 있는 경로의 수를 구하는 문제입니다. 최단 경로를 찾는 문제가 아닌, 모든 경로를 다 찾는 문제임을 고려해야 합니다.완전 탐색(brute-force)으로 구현한다면 쉽게 구현할 수 있는 문제입니다. 하지만 완전 탐색으로 구현한다면 입력의 사이즈, 즉 n과 m이 꽤 크고 (최대 n 동적 계획법을 사용합니다.동적 계획법, top-down 기반의 memoization 기법을 사용하면 탐색했던 경로를 다..