[백준] 2169 로봇 조종하기💫

백준 2169 로봇 조종하기

• https://www.acmicpc.net/problem/2169

한 줄 씩 처리하는 풀이

• 맨 첫줄은 (1,1)에서 시작하기 때문에 오른쪽으로 진행하는 것만 가능하다

• 두번 째 줄 부터 각 자리에 오는 방법은 다음과 같이 2가지가 가능하다
  1. 바로 위에서 내려오거나 왼쪽에서 오기
  2. 바로 위에서 내려오거나 오른쪽에서 오기
  두 경우를 각각 leftdp, rightdp에 계산하여 둘 중 최댓값을 최종 dp에 저장한다

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 1005;

int N, M;
int value[MAXN][MAXN];
int dp[MAXN][MAXN];

void getdp() {
	//맨 첫줄
	//오른쪽에서 오는 경우 뿐
	dp[1][1] = value[1][1];
	for (int col = 2; col <= M; ++col)
		dp[1][col] = dp[1][col-1] + value[1][col];

	//두번째 줄 부터 마지막 줄 까지
	for (int row = 2; row <= N; ++row) {
		int leftdp[MAXN];
		int rightdp[MAXN];

		//바로 위에서 내려오거나 왼쪽에서 오기
		leftdp[1] = dp[row-1][1] + value[row][1];
		for (int col = 2; col <= M; ++col)
			leftdp[col] = max(dp[row-1][col], leftdp[col-1]) + value[row][col];

		//바로 위에서 내려오거나 오른쪽에서 오기
		rightdp[M] = dp[row - 1][M] + value[row][M];
		for (int col = M-1; col >= 1; --col)
			rightdp[col] = max(dp[row - 1][col], rightdp[col + 1]) + value[row][col];

		//둘 중 최댓값을 최종 dp에 저장
		for (int col = 1; col <= M; ++col)
			dp[row][col] = max(leftdp[col], rightdp[col]);
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			cin >> value[i][j];

	getdp();
	cout << dp[N][M];

	return 0;
}

⚡방향별 처리하는 풀이

• 나중에 추가하도록 하겠다

📌참고자료

• 백준 2169 로봇 조종하기 풀이 (한 줄 씩 처리)
  https://lovelyunsh.tistory.com/108category=970038

• 백준 2169 로봇 조종하기 풀이 2 (방향별 처리)
  https://yabmoons.tistory.com/353