[백준OJ] 11048번 이동하기

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

11048번: 이동하기

---

 

 

-풀이-

3x3 배열을 예시로 들어보자

1번 인덱스	2번 인덱스	3번 인덱스
4번 인덱스	5번 인덱스	6번 인덱스
7번 인덱스	8번 인덱스	9번 인덱스

먼저 1번 인덱스에서 시작이므로, 1번인덱스 까지 최대로 얻을 수 있는 사탕은 1번인덱스에있는 사탕의 개수이다.

2번인덱스에서 얻을 수 있는 사탕의 최대 개수는, 위쪽은 없으므로 비교 불가이기때문에, 1번+2번의 개수가 될것이다.

3번 인덱스에서 얻을 수 있는 사탕의 최대 개수는, 위에서 내려오는 경우가 없기때문에 1번+2번+3번의 개수가 될것이다.

4번 인덱스에서 얻을 수 있는 사탕의 최대 개수는, 1번에서 내려오는 경우밖에 없기때문에 ( 문제에서 이동조건에 대한 조건에 의해) 1번에서 내려오는 경우뿐이므로, 1번+4번의 개수가 될것이다.

 

5번을 보자. 5번에 도달할 수 있는 경우는 3가지가 있다. 2번인덱스에서 내려오는 경우와, 4번 인덱스에서 옆으로 이동하는 경우, 1번 인덱스에서 대각선으로 내려오는 경우가 있다. 현재까지 탐색을 하면서 1번, 2번, 4번은 각각 자기 구역까지 도달했을때, 얻을 수 있는 경우의 최대 개수가 저장이 되어있다. 따라서 이 세 구역중, 사탕이 현재까지 가장 많은 구역에서 5번으로 이동을 한다면, 가장 많은 사탕을 얻을 수 있게된다.

 

6번도 마찬가지이다. 현재까지 2번,3번,5번은 각각 자기구역에 도달했을때의 최대 사탕의 개수를 가지고있다. 따라서 6번까지 도달했을때의 사탕의 최대개수를 구하기 위해서는 2번, 3번, 5번중 가장 사탕이 많은 구역+자신의 구역의 사탕을 해주면 되는것이다.

 

 

-시간복잡도-

NxM 배열을 한번 탐색하며 구할 수 있으므로, O(NM) 이 된다.

 

-코드-

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

int arr[1001][1001];
int dp[1001][1001] = { 0 };
int mv[3][2] = { {-1,-1},{-1,0},{0,-1} };
int n, m;

bool isIn(int i, int j) {
	return i >= 0 && i < n&&j >= 0 && j < m;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			dp[i][j] = arr[i][j];
		}
	}

	int result = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 3; k++) {
				int bi = i + mv[k][0];
				int bj = j + mv[k][1];

				if (isIn(bi, bj)) {
					dp[i][j] = max(dp[i][j], arr[i][j] + dp[bi][bj]);
				}
			}
		}
	}
	cout << dp[n-1][m-1];
}