[코딩테스트 연습] 등굣길

 

문제: https://programmers.co.kr/learn/courses/30/lessons/42898#

---

DP 문제입니다.

dp[i][j] = dp[i-1][j] + dp[i][j-1] 의 관계가 성립함을 알 수 있습니다.

 

단, 전처리에서 중요한 것이 있는데요.

 

맨 처음 경로 계산을 위해 가장 자리 값들을 1로 셋팅 할 때 아래와 같이 할 수 있습니다.

집	1	1	1
1
1
1			학교

 

그런데, 특정 지점에서 웅덩이가 등장했다면, 그 뒷 지점은 전부 방문할 수 없으므로 0으로 놔둬야 합니다.

집	웅덩이	0	0
1
1
1			집

 

이 부분만 신경써주면 무난히 DP로 해결할 수 있습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG42898.cc