프로그래밍 문제 풀고, 시험기간동안 풀었던 문제를 정리하는 시간을 가졌다.
<br> <br>
시험 기간 이슈로 '공부하기 싫을 때 몇 개 풀고 시험 끝나면 다 정리해서 올려야지~' 했는데 알고리즘 과목 준비로 dp문제를 한 바가지 풀어서 다 정리할 수 없게 되었다 ... 풀면서 뭔가 깨닫고 배운 게 있는 문제들만 정리하기로 결정함!
우선 이 '등굣길'무제는 내가 dp를 확실히 이해하게 해준 아주 고마운 문제다. 문제를 제대로 안 읽은 탓에 삽질을 아주 기가 막히게 하고, 대신 dp의 2가지 풀이법을 체화?시킬 수 있었다. 이 문제를 풀기 전까지 뭔가 뜬구름 잡는 느낌이라 문제를 풀면서도 확신이 없었는데 이 문제를 계기로 확실히 깨달았다!!! 차근차근 정리를 해보겠다.
가장 먼저 알고리즘 수업에서 느낀 dp문제 해결 방법은 'case에 따라 return 방식을 달리하자.'였다. 만약 이런 형태라면 1을 return 하고 아니라면 a와 b 중 작은 것을 return 하는 그런 식의 풀이법이 많았고 이 문제 역시 그런 흐름으로 문제를 풀었다.
위와 같이 흐름을 정리했다. 테두리에서 웅덩이가 생기면 웅덩이를 기점으로 그 다음 블록들은 최단 경로로 갈 수 없게 된다. (가로에선 웅덩이의 오른쪽, 세로에선 웅덩이의 아래쪽) 그래서 1. 집 2. 웅덩이 3. 테두리인데 웅덩이 다음 4. 그 외 테두리가 아닌 애들 로 경우를 나누어 코드를 작성했다.
<br><br><br>