백준다이나믹

[백준 2169] 로봇 조종하기 C++

www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 이 문제는 1,1에서 시작한 로봇이 N, M까지 도달하는 경로 누적 합 중 최대값을 구하는 문제 입니다. DFS로, 각 공간마다 방향 왼쪽, 아래, 오른쪽으로 나누어서 풀면 되지만, 문제 조건 중에 N, M 제한이 1,000이기 때문에, 매번 갔던 길을 또 계산한다면 시간 복잡도가 어마하게 나올 것으로 생각되었습니다. 다이나믹프로그래밍을 사용해서, 각 지점에서 출발해서 N,M에 도달할 때의 최댓값을 저..