[백준] 11048번. 이동하기

[백준] 11048번. 이동하기

1. 문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

2. 입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

3. 출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

4. 풀이

• 등굣길 문제와 거의 같다.
• (r, c)에서 얻을 수 있는 캔디의 최댓값은 (r-1, c)에서 얻을 수 있는 캔디와 (r, c-1)에서 얻을 수 있는 캔디의 최댓값에 현재 칸의 캔디 값을 더한 값이다.
  어차피 위로나 왼쪽으로는 못 가니까 두 개만 생각해주면 된다. 대각선은 왜 있는지 모르겠다 어차피 오른쪽 가고 아래로가면 대각선이고 캔디는 최소 0이니까 대각선으로 가서 이득을 볼 상황이 전혀 없는데 왜 있는지 이해 불가
• (n, m)에서 얻을 수 있는 캔디의 최댓값을 출력하면 된다.

5. 처음 코드와 달라진 점

• 2중 loop에서 j가 i로 되어 있어서 오류가 났다.
• 하루 종일 BFS하고 있다가 2차원 배열 나오니까 또 BFS를 하려고 했는데 오류가 나서 틀렸다. 근데 사실 위의 이유로 난 거였다.
  제대로 했어도 시간 초과였을 것 같긴하다.
• 그래서 뒤로 갈 수 없다는 걸 깨닫고 DP로 풀었다.

6. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int map[1000][1000];
int candy[1000][1000];


int main() {
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++)
			cin >> map[i][j];
	}

	candy[0][0] = map[0][0];
	for (int i = 1; i < m; i++){
		candy[0][i] = map[0][i] + candy[0][i - 1];
	}
	for (int i = 1; i < n; i++){
		candy[i][0] = map[i][0] + candy[i - 1][0];
	}

	for (int i = 1; i < n; i++){
		for (int j = 1; j < m; j++) {
			candy[i][j] = max(candy[i - 1][j], candy[i][j - 1]) + map[i][j];
		}
	}

	cout << candy[n - 1][m - 1];
}