[C++] BOJ(백준) 2169 로봇 조종하기

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

2169번: 로봇 조종하기

 

DP 문제다.

그래프 형태의 DP문제로 어떻게 해결할지 고민했다.

 

처음에는 BFS로 접근을 하였으나 굳이? 싶었고, 시간초과가 날 것 같았다.

 

두 번째 떠올린 방법은 아래로 움직이는 것은 따로 고려해줄 것이 없으므로 dp[i][j] = dp[i - 1][j]를 해준 후

해당 지점에서 왼 오로 퍼지면서 중복 방문을 방지하도록 했다.

시간 초과를 예상하긴 했지만 반례가 없을 것 같아 시도 했다.

답이 한 번에 나와 신나게 넣어봤지만 역시나 시간초과다.

 

세 번째 방법은 비슷하지만 불필요한 연산을 줄인 방법이다.

왼쪽으로 움직이는 DP 배열과 오른쪽으로 움직이는 DP 배열을 따로 생성한 뒤

각각의 구간에서 둘 중 최댓값을 찾는 방법이다.

 

배열을 0번 부터 사용하는 것을 선호하나 왼 오 이동을 위해 테두리 여백을 생성했다.

dp 배열을 초기화 할 때 문제점이 있었다.

1. 0으로 초기화

    수가 음수도 들어오기 때문에 0으로 초기화를 하면 잘못된 답을 가져온다.

2. 입력 칸 만큼 초기화

    입력과 동시에 입력 칸에 대해서만 dp 배열을 초기화 했는데

    이러면 테두리에 대해서는 초기화가 되지 않기 때문에 잘못된 답을 가져온다.

 

#include <iostream>
#include <climits>
using namespace std;

int n, m;
int arr[1001][1001];
int dpLeft[1002][1002];
int dpRight[1002][1002];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) cin >> arr[i][j];

	for (int i = 0; i <= n + 1; i++)
		for (int j = 0; j <= m + 1; j++) {
			dpLeft[i][j] = INT_MIN;
			dpRight[i][j] = INT_MIN;
		}

	dpLeft[1][1] = dpRight[1][1] = arr[1][1];
	for (int i = 2; i <= m; i++) {
		dpLeft[1][i] = dpLeft[1][i - 1] + arr[1][i];
		dpRight[1][i] = dpRight[1][i - 1] + arr[1][i];
	}

	for (int i = 2; i <= n; i++) {
		for (int j = m; j > 0; j--)
			dpLeft[i][j] = max(dpLeft[i - 1][j], dpLeft[i][j + 1]) + arr[i][j];
		for (int j = 1; j <= m; j++)
			dpRight[i][j] = max(dpRight[i - 1][j], dpRight[i][j - 1]) + arr[i][j];
		for (int j = 1; j <= m; j++) {
			dpLeft[i][j] = max(dpLeft[i][j], dpRight[i][j]);
			dpRight[i][j] = dpLeft[i][j];
		}
	}
	cout << dpLeft[n][m];
}

(´▽`ʃ♡ƪ)