[백준 2619 - C++] 로봇 조종하기

⬇️ 문제 출처

백준 2169 : 로봇 조종하기

💡 접근 방법

처음에는 완전 탐색의 방법으로 접근했다... 하지만 시간초과...
그래서 dp로 생각해보았지만, 안풀려서 포기상태였다.
하지만 다시 도전!
문제에서 주어진 조건이 위쪽으로는 이동할 수 없기에 한 행에서는 무조건 왼쪽에서 오거나 오른쪽에서 와야한다. 그것을 기준으로 코드를 다시 짜봤다.

✏️ 풀이

위쪽으로 갈 수 없기에 한 행의 왼쪽에서 올 때의 최댓값을 왼쪽에서 올 때, 위쪽에서 올 때 중 최댓값과 탐사한 지역의 가치를 더한걸 left_max_price 배열에 저장하고, 반대로 오른쪽에서도 똑같이 right_max_price에 저장해줬다. 그 후 탐색한 지역의 left_max_price, right_max_price 값을 비교해 최댓값을 dp에 넣고 다음 행으로 이동했다.

⌨️ 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <string>
#include <queue>
#include <cstring>
#include <tuple>
#include <cmath>
#include <math.h>
#define MAX_N 1000+5
#define endl "\n"
const int INF = 987654321;
typedef long long ll;
using namespace std;
int arr[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];
int left_max_price[MAX_N];
int right_max_price[MAX_N];

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

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

	for (int i = 1; i <= M; i++) {
		dp[1][i] += arr[1][i] + dp[1][i - 1];
		//cout << dp[1][i] << " ";
	}
	for (int i = 2; i <= N; i++) {
		memset(left_max_price, 0, sizeof(left_max_price));
		for (int k = 1; k <= M; k++) {
			if (k == 1) left_max_price[k] = dp[i - 1][k] + arr[i][k];
			else left_max_price[k] = max(left_max_price[k - 1], dp[i - 1][k]) + arr[i][k];
		}
		memset(right_max_price, 0, sizeof(right_max_price));
		for (int k = M; k >= 1; k--) {
			if (k == M) right_max_price[k] = dp[i - 1][k] + arr[i][k];
			else right_max_price[k] = max(right_max_price[k + 1], dp[i - 1][k]) + arr[i][k];
		}
		for (int j = 1; j <= M; j++) {
			dp[i][j] = max(left_max_price[j], right_max_price[j]);
		}
	}
	
	cout << dp[N][M] << endl;
}

🔥🔥🔥

제발 생각 좀 더 하고 풀자...