woody

문제소개 해결과정 첫 번째 시도는 Bottom-up 방식이었다. dp[i][j]를 출발지부터 현재 위치까지 올 수 있는 경로의 개수로 생각했고, 주변의 4개의 지점에서 내 쪽으로 올 수 있는 애들의 경로의 개수를 합해주면 될거라고 생각했다. 하지만 이런 방식을 선택한다면 이전의 dp배열들이 계속 갱신되어야한다. 뒤늦게 경로가 추가될 수 있기 때문이다. 따라서 이 문제를 Bottom-up 방식으로 해결하는 시도 자체가 스스로 어려운 길로 빠지는 것이라고 생각했다. Top-down 방식으로 이 문제를 접근한다면, dp[i][j]는 현재 위치에서 도착지로 갈 수 있는 경로의 개수가 된다. 따라서 재귀함수 안에 점화식은 다음과 같은 형태를 이룬다. static int dfs(int y, int x) { if (..

- 문제설명 & 제한사항 - 예시 - 해결과정 작은 문제에서 큰 문제를 해결해나가도록 재귀함수를 호출하자. 1. n개의 원반을 목적지까지 옮기기 위해서는 n-1개의 원반을 먼저 경유지로 옮긴다. 2. 남아있는 가장 큰 원반을 목적지로 옮긴다. 3. 경유지에 있는 n-1개의 원반을 목적지로 옮긴다. 재귀 호출의 흐름을 파악하려고 하면 이 문제는 상당히 복잡해진다. 큰 흐름만 살펴보자. 1) 원반이 1개인 경우, 즉 가장 작은 상황부터, 이동을 마치고 2개, 3개, 4개, 5개로 확장해서 생각해보자. 2) 1개의 원반만 있으므로 바로 목적지로 옮길 수 있다. 현재 재귀호출을 종료하고 상위 재귀호출(원반2개)로 돌아간다. 3) 이전 재귀호출의 입장(원반 1개 이동)에서는 목적지로 원반을 옮긴 것이지만, 현재 ..