[백준] 11048번 - 이동하기 / C++

문제

준규는 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)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

 

입력

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

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

 

출력

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

 

코드

#include <iostream>

using namespace std;

int N;
int M;
int candy[1001][1001];
int m[1001][1001];

int main()
{
	int x;
	int y;
	int prev;
	int answer;

	cin >> N >> M;
	if (N < 1 || N > 1000 || M < 1 || M > 1000)
	{
		return -1;
	}
	for (y = 1; y <= N; y++)
	{
		for (x = 1; x <= M; x++)
			cin >> candy[y][x];
	}
	for (y = 1; y <= N; y++)
	{
		for (x = 1; x <= M; x++)
		{
			prev = max(m[y - 1][x], max(m[y][x - 1], m[y - 1][x - 1]));
			m[y][x] = prev + candy[y][x];
		}
	}
	answer = m[N][M];
	cout << answer << endl;

	return 0;
}

 

동적프로그래밍을 사용하는 문제이다. (1, 1)부터 시작하여 각 위치로 이동하며 모을 수 있는 사탕의 최대 개수를 m 배열에 저장한다.

(y - 1, x) (y, x - 1) (y - 1, x - 1)으로부터 (y, x)에 도달할 수 있기 때문에 앞선 세 좌표에서 모은 사탕 개수를 비교하여 최댓값을 구한다. 이 최댓값과 현재 위치에서의 사탕 개수를 더하면 현재 위치 (y, x)로 이동하며 모은 사탕 개수의 최댓값이 된다. 모든 좌표에 대하여 각 좌표에서의 사탕 개수의 최댓값을 구하고, 마지막 좌표인 (N, M)의 사탕 개수의 최댓값이 answer가 된다.

 

링크

11048번: 이동하기

inbdni/Baekjoon