BOJ 1520

아 진짜 글쓰기 귀찮네... 분명 나중에 까먹을게 뻔해서 이렇게라도 적어놓아야 되는데... 진짜 귀찮다...

그래도 계속 쓰다보면 나아지겠지...
이 내리막길이라는 문제는 처음에 bfs로 접근했다가 메모리 초과가 났는데, bfs외에는 떠오르지가 않아서 계속 bfs로 하다가 결국 포기했었다. 그래서 이번에 풀이를 다시 보고 dp로 접근하려고 했는데, 이제는 풀이가 잘 이해가 안되는 것이었다...

풀이에서는 d[i][j]를 (i, j)에서 (m, n)까지 가는 내리막길 방법의 수로 정의했다.
음 나는 d[i][j]를 (0, 0)에서 (i, j)까지 가는 방법의 수라고 생각했기 때문에 왜 저렇게 해야되는지 이해가 안되었는데... 계속 생각해보니...
중요한 건 저 정의들이 아니라 재귀로 푸냐 아니냐 인 것 같다.

이 문제는 for문을 이용한 dp로 풀기가 매우 어렵다고 한다..(가능은 한건가??) 여튼 내 생각에는 가능한지도 모르겠는데... 일단 내 생각으로는 for문으로 할 경우, 어디서 부터, 즉 어떤 순서로 d[i][j]를 채워나가야 할지 알기가 힘들다는 것이다. 보통 dp에서는 d[i][j]를 채우면 그것을 그대로 쓰는데, for문으로 해서 작은 것부터 채워나가면 이게 또 갱신될 수도 있고, 갱신되기 전의 값을 사용해서 잘못된 값이 구해질 수도 있고... 복잡하다...

하지만 재귀를 쓰면 달라진다. 편하다.

여튼 이 문제는 별거 아닌 것 같지만 정말 좋은 문제 같다.

그래서 일단 내 생각대로 재귀를 만들어서 제출했더니 맞았다.
이제 백준님의 풀이대로 한번 해보려고 한다.