맵, 디피맵이 있습니다. 일단 맵을 저장해두고, 라인도 하나 저장해두는데, 라인 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; } |