[BAEKJOON] 2169 로봇 조종하기

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() {     vector<vector<int>>map(1001, vector<int>(1001));       int row, col;     scanf("%d %d", &row, &col);       for (int x = 0; x < row; x++)         for (int y = 0; y < col; y++)             scanf("%d", &map[x][y]);       vector<vector<int>>DP(2, vector<int>(1001, 0));;       for (int y = 0; y < col - 1; y++) map[0][y + 1] += map[0][y];       for (int x = 1; x < row; x++)     {         DP[0][0] = map[x][0] + map[x - 1][0];         for (int y = 1; y < col; y++)             DP[0][y] = max(DP[0][y - 1], map[x - 1][y]) + map[x][y];           DP[1][col - 1] = map[x][col - 1] + map[x - 1][col - 1];         for (int y = col - 2; y >= 0; y--)             DP[1][y] = max(DP[1][y + 1], map[x - 1][y]) + map[x][y];           for (int y = 0; y < col; y++)             map[x][y] = max(DP[0][y], DP[1][y]);     }       printf("%d", map[row - 1][col - 1]);       return 0; }

LG CodeMonster에서 비슷한 문제가 나왔었다

그 문제는 왼쪽으로는 갈 수 없고 오른쪽, 위, 아래로 갈 수 있었다

이 문제도 비슷하다

오른쪽 왼쪽 아래로는 갈 수 있지만 이번에는 위쪽으로는 갈 수 없다

어려운 문제였다

비슷한 문제를 조금 더 풀어보고 싶다

1. 맨 윗 줄은 오른쪽으로 밖에 갈 수 없다

지나온 길은 다시 지나갈 수 없기 때문이다.

2. 그 다음 줄부터는 새로운 규칙을 적용해야한다

오른쪽으로 갈 때의 최대와 왼쪽으로 갈 때의 최대를 보자

 2-1. 오른쪽으로 갈 때

: 맨 처음은 위에서 내려와야 한다

 오른쪽으로 가면서 내 위에서 내려오는 것과 왼쪽에서 오는 것의 max값에서 자신의 값을 더하면 된다

 2-2. 왼쪽으로 갈 때

: 맨 마지막부터 시작해야한다. 마지막은 위에서 내려와야 한다

 왼쪽으로 가면서 내 위에서 내려오는 것과 오른쪽에서 오는 것의 max값에서 자신의 값을 더하면 된다.

오른쪽 위 아래의 최대를 구하고 싶기 때문에 구한 2-1과 2-2의 최대를 구해서 저장해놓는다

위의 순서를 반복해서 마지막에 오는 것이 최대값이다.

배우면서 성장하는 거겠지..