Algorithm/BOJ
[BOJ] 백준 1520번 내리막길 c++
buru_bum
2021. 11. 22. 18:21
BOJ 문제 링크: https://www.acmicpc.net/problem/1520
1520번: 내리막 길
첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다.
www.acmicpc.net
각 칸마다 높이가 적혀있는 지도가 입력으로 주어진다. 현재지점보다 낮은 지점으로 상하좌우 이동이 가능하다.
좌측 상단에서 시작해서 우측 하단으로 도착하는 경우의 수를 구하는 문제이다.
현재 위치 (curX, curY) 에서 도착지점 (n-1, m-1) 까지 갈수있는 경로의 수를 cache[curX, curY]에 저장하는 다이나믹 프로그래밍을 이용하면 문제를 풀 수 있다.
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!