[백준] 1520번 - 내리막 길 (C++, 파이썬) 문제 및 풀이

문제) 백준 - 동적 계획법 (Dynamic Programming) - 내리막 길

-> www.acmicpc.net/problem/1520

1520번: 내리막 길

 

각 지점까지 이동할 수 있는 경로의 수를 저장한 2차원 리스트(dist)에 메모이제이션을 적용한다. dist 리스트의 초기값을 -1로 선언해 방문 여부를 판단한다. 각 지점까지 이동할 수 있는 경우의 수는 dfs를 이용하여 경로가 겹치는 지점에서 서로의 경로 수를 합친다. 

 

 

Python 소스 코드)

 

C++ 소스 코드)

 

 

Python Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/1520_%EB%82%B4%EB%A6%AC%EB%A7%89%20%EA%B8%B8.py

GitHub - Chocochip101/BOJ_Solution

 

C++ Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/1520_%EB%82%B4%EB%A6%AC%EB%A7%89%20%EA%B8%B8.cpp

GitHub - Chocochip101/BOJ_Solution