[백준] 2169번 - 로봇 조종하기

링크

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

2169번: 로봇 조종하기

풀이

로봇은 아래, 오른쪽 ,왼쪽 으로만 갈수 있다고 한다.

이때 맨 좌표의 맨 윗줄은 항상 오른쪽으로만 갈수 있기 때문에 첫줄은 오른쪽으로 값을 더해 준다.

이후 2번째 줄부터 N번째 줄까지는 x, y좌표에 도착 하려면 위, 오른쪽, 왼쪽에서 내려올수 있는 경우의 수가 있기 때문에

 위에서 내려와 오른쪽으로 가는 값을 tmp[0] 배열에 저장하고

 위에서 내려와 왼쪽으로 가는 값을 tmp[1] 배열에 저장하고

 

tmp[0], tmp[1]를 비교하여 큰값을 dp 배열에 넣어주면 된다.

#include<iostream>
#include<algorithm>

#define SIZE 1010
using namespace std;

int board[SIZE][SIZE];
int dp[SIZE][SIZE];
int tmp[2][SIZE];

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

	int N, M; cin >> N >> M;

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


	for (int j = 1; j <= M; j++) {
		dp[1][j] += dp[1][j - 1] + board[1][j];
	}

	for (int i = 2; i <= N; i++) {
		tmp[0][0] = dp[i - 1][1];
		for (int j = 1; j <= M; j++) {
			tmp[0][j] = max(dp[i - 1][j], tmp[0][j - 1]) + board[i][j];
		}

		tmp[1][M + 1] = dp[i - 1][M];
		for (int j = M; j > 0; j--) {
			tmp[1][j] = max(dp[i - 1][j], tmp[1][j + 1]) + board[i][j];
		}

		for (int j = 1; j <= M; j++) {
			dp[i][j] = max(tmp[0][j], tmp[1][j]);
		}
	}

	cout << dp[N][M];
}