44. 출근길은 즐거워 (재귀, 메모이제이션, 동적 프로그래밍)

1. 개요

출근길 문제는 쉬움.

2차원 배열의 미로 문제와 같음.

2차원 배열의 각 좌표는 즐거워씨가 출근할 때 갈 수 있는 경치 지점.

2차원 배열의 각 값은 즐거워씨가 그 좌표를 들렸을 때 경치의 아름다움 크기.

결국 재귀, 메모이제이션, 동적 프로그래밍 연습 문제.

2. 문제

즐거워 씨가 출근할 때, 최단 거리이면서 가장 경치가 아름다운 길을 찾으시오.

(재귀, 메모이제이션, 동적 프로그래밍, 경로 탐색 알고리즘을 작성)

3. 코드

3-1) get_max_view()

3-2) get_max_view_MEMO()

3-3) get_max_view_DP()

3-4) trace_path()

3-5) 출력 5,5

3-6) 출력 10,10

4. 정리

이제 재귀 점화식만 알면 쉽게 짤 수 있겠다. 결국 재귀란 점화식 찾아내는 것이 더 까다로운 것.