이동하기 (feat. 백준, 11048번)

이동하기
https://www.acmicpc.net/problem/11048

11048번: 이동하기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/11048
#include<iostream>
#include<algorithm>
using namespace std;
int arr[1001][1001], dp[1001][1001];
int main(void) {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, M;
	cin >> N >> M;
	for (register int x = 1, y; x <= N; ++x)
		for (y = 1; y <= M; ++y)
			cin >> arr[x][y];
	dp[1][1] = arr[1][1];
	for (register int x = 1; x <= N; ++x)
		for (register int y = 1; y <= M; ++y) {
			dp[x][y + 1] = max(dp[x][y + 1], dp[x][y] + arr[x][y + 1]);
			dp[x + 1][y] = max(dp[x + 1][y], dp[x][y] + arr[x + 1][y]);
			dp[x + 1][y + 1] = max(dp[x + 1][y + 1], dp[x][y] + arr[x + 1][y + 1]);
			dp[x + 1][y + 1] = max(dp[x + 1][y], max(dp[x][y + 1], dp[x + 1][y + 1]));
		}
	cout << dp[N][M] << endl;
	return 0;
}
// *&)*@*

1	2
3	?

1. 위 (2,2)는 (1,1) + (1,2) / (1,1) + (2,1) / (1,1) + (2,2) 중 가장 큰 값이 오게 됩니다.
2. 따라서 그 수식을 그대로 가져가면 답이 됩니다.