백준] 11048 - 이동하기

시간 제한 : 1초

메모리 제한 : 256MB

입력

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

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

출력

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

소스코드

#include <iostream>
using namespace std;
int arr[1001][1001], dp[1001][1001] = { 0, };
int main(void)
{
	int n, m, max;
	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 <= n; i++)
		dp[i][1] = dp[i - 1][1] + arr[i][1];
	for (int i = 1; i <= m; i++)
		dp[1][i] = dp[1][i - 1] + arr[1][i];

	for (int i = 2; i <= n; i++)
	{
		for (int j = 2; j <= m; j++)
		{
			max = dp[i - 1][j] < dp[i][j - 1] ? dp[i][j - 1] : dp[i - 1][j];
			max = max < dp[i - 1][j - 1] ? dp[i - 1][j - 1] : max;
			dp[i][j] = max + arr[i][j];
		}
	}
	cout << dp[n][m];
}

Tip

아주 간단한 다이나믹 프로그래밍으로, (R,C) 지점에서의 최적해는 (R-1,C), (R, C-1), (R-1,C-1) 중 가장 큰 값이다.