[Programmers 코딩테스트 고득점 Kit] 등굣길

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

앞선 문제에 이어 전형적인 DP 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 웅덩이 좌표를 set에 저장해줍니다.

2. 오른쪽, 아래쪽으로만 움직일 수 있으므로 DP의 점화식을 [y, x]까지의 최단 경로 = [y - 1, x]까지의 최단 경로 + [y, x -1]까지의 최단 경로로 정의해줍니다.

3. 2번 식을 적용하여 이중 반복문을 돌리는데 웅덩이 위치는 밟을 수 없으므로 0으로 초기화하고 나머지 좌표에 대해서는 점화식을 적용해줍니다.

4. 3번을 통해 구한 [n, m]까지의 최단경로 수를 반환해줍니다.

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~