https://www.acmicpc.net/problem/2169골드2풀이 방법단순 dfs로 하면 시간 초과 발생합니다. (시간 복잡도: O(3^(N * M))N, M(1≤N, M≤1,000)현재 문제는 “각 칸까지 올 수 있는 최적 해를 모아 두고, 그 위에서 다음 칸의 최적 해를 구한다”가 목표→ DP 생각하기이동 경로 가능 경로: 오른쪽, 왼쪽, 아래따라서 위에서 부터 오른쪽에서 왼쪽으로 갈 때 max값과 왼쪽에서 오른쪽으로 갈 때 max값을 구한 뒤두 값중 더 큰 값을 아래로 내려주면 된다.이때 시작은 0,0에서 하기 때문에 이 경우에는 왼쪽에서 오른쪽의 경우만 생각하면 된다.dp 시간 복잡도매 행마다 두 번의 선형 스윕을 수행하므로 O(N×M)코드import java.util.*;import j..