์•Œ๊ณ ๋ฆฌ์ฆ˜

  • (1,1)์—์„œ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ๋ชจ๋“  ์ ์„ ๋Œ€์ƒ์œผ๋กœ visit (i -1, j), (i, j-1), (i-1,j-1) ์ด ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์  ์ค‘ ๊ฐ€์žฅ ํฐ ์ ์„ visit(i,j) ์— ์ €์žฅํ•œ๋‹ค.

์ฝ”๋“œ

#include <iostream>
 
using namespace std;
 
int visit[1010][1010], n, m, map[1010][1010];
 
int max(int a, int b) {
	return a > b ? a : b;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> map[i][j];
		}
 
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			visit[i][j] = map[i][j] + max(max(visit[i - 1][j], visit[i][j - 1]), visit[i - 1][j - 1]);
 
	cout << visit[n][m];
}