백준 2169 로봇 조종하기 디피문제 정답 참조

맵, 디피맵이 있습니다. 일단 맵을 저장해두고, 라인도 하나 저장해두는데, 라인 0에는 라인1에는 무엇을 저장하는가요. 토탈은 변수가 사용안됩니다. 먼저 왼쪽, 오른쪽 위에서 아래로 내려오는 3가지 방향이 있으므로, 이 3가지 내려오는 방향 중에 가장 큰 것을 저장해 나가면 됩니다. 1. 첫줄은 오른쪽으로만 저장해 나갈 수 있으므로, 저장해둡니다. 2. 그 다음에 2행부터는 일단 라인 0,1 에 위에서 내려오는 값들을 저장해 둡니다. 3. 위, 왼 값을 비교해서 큰 값을 라인 0에 저장을 합니다. 4. 위, 오 값을 비교해서 큰 값을 라인 1에 저장을 합니다. 5. 라인 0과 1을 비교해서 큰 값을 프리맵에 저장을 하면 됩니다.  마지막 도달하는 점의 값을 출력하면 됩니다.  일단 이렇게 알아두고 넘아가도록 합니다. 디피 문제. 일단 문제에서 엔 곱 엔인데 dfs 풀기란 시간 초과가 나옵니다.

/* 처음으로 디피 문제를 풀어봅니다. 여기서 디피란 한 메모리에 저장을 해두고, 그 값을 계속해서 사용한다는 의미입니다 */ #include <iostream> #include <algorithm> using namespace std; #define SIZE 1005 // 1005 int map[SIZE][SIZE]; int primap[SIZE][SIZE]; int main(void) { int N, M; int line[2][1000]; int total = 0; cin >> N >> M; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> map[i][j]; } } primap[0][0] = map[0][0]; for (int i = 1; i < M; i++) { primap[0][i] = primap[0][i - 1] + map[0][i]; } for (int height = 1; height < N; height++) { for (int row = 0; row < M; row++) { line[0][row] = line[1][row] = primap[height - 1][row] + map[height][row]; } for (int row = 1; row < M; row++) { line[0][row] = max(line[0][row], line[0][row - 1] + map[height][row]); } for (int row = M - 2; row >= 0; row--) { line[1][row] = max(line[1][row], line[1][row + 1] + map[height][row]); } for (int row = 0; row < M; row++) { primap[height][row] = max(line[0][row], line[1][row]); } } cout << primap[N - 1][M - 1] << endl; return 0; }