BOJ 11048 이동하기

www.acmicpc.net/problem/11048

11048번: 이동하기

 

(1, 1)에서 (n, m)으로 가야 하는데 오른쪽, 밑, 오른쪽 밑으로 가면서 가져갈 수 있는 가치 중 최댓값을 구하면 된다.

우선 오른쪽 밑 대각선으로 가는 부분은 없다고 생각해도 된다.

왜나면 '무조건' 위나 왼쪽에서 챙겨가는 것이 더 이득이기 때문이다.

따라서 그냥 2차원 누적 합으로 생각해도 된다.

 

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

int n, m, x, d[1001][1001];

int main() {
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &x);
			d[i][j] = max(d[i - 1][j], d[i][j - 1]) + x;
		}
	}

	printf("%d\n", d[n][m]);

	return 0;
}