[BAEKJOON] 2169 로봇 조종하기

#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의 최대를 구해서 저장해놓는다

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

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