IT 개발 돼지의 일상

출저 : https://www.acmicpc.net/problem/1890 "DP 와 2^63" 전형적인 DP 문제로서 Top-down 방식의 메모이제이션을 사용한다. Start 부터 시작해서 End 까지 탐색한다. 검색 중에 End 에 도착했다면 한 가지 방법이 있는 것이므로 1을 리턴하고 이 값은 함수를 호출한 dp[x] 에 누적된다. 아래 예를 보면 4,5,6 번 노드가 이와 같다. 이런식으로 "누적"을 하게 되면 해당 노드에서 End로 갈 수 있는 방법의 수가 dp[x]에 저장된다. DFS 나 BFS 로 풀면 시간초과가 날 것이 왜 dp를 쓰면 시간이 단축 되나? 라는 질문에 답은 7번 노드를 보면 된다. 7번 노드까지 탐색한 후에 6번 노드의 dp값을 체크하였더니 1이 저장되어 있더라. 6번 이..