11048번: 이동하기

📝 Memo

Memory : 9724 KB

Time : 112 ms

🖥️ Code

#include <bits/stdc++.h>
#include <algorithm>
int max(int a, int b, int c)
{
	if (a >= b && a >= c)
		return a;
	if (b >= a && b >= c)
		return b;
	return c;
}

int main()
{
	int arr[1001][1001];
	int dp[1001][1001];

	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf("%d",&arr[i][j]);
	dp[0][0] = arr[0][0];
	for(int i=1;i<n;i++)
		dp[i][0] = dp[i-1][0] + arr[i][0];
	for(int j=1;j<m;j++)
		dp[0][j] = dp[0][j-1] + arr[0][j];
	for(int i=1;i<n;i++)
		for(int j=1;j<m;j++)
			dp[i][j] = std::max({dp[i-1][j-1],dp[i-1][j],dp[i][j-1]}) + arr[i][j];
	printf("%d",dp[n-1][m-1]);
}