11048번: 이동하기

Memo

• 1, 1부터 열, 행 순으로 순회하면서 자신의 위치로 올 수 있는 값들 중에 최대값과 현재 자신의 위치의 값을 더합니다.

Code

제출 날짜

2021/03/24

메모리

9844 KB

시간

64 ms

#include <iostream>
#include <algorithm>

int N, M;

int dp[1001][1001];
int maze[1001][1001];

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> N >> M;
	for (int i = 1 ; i <= N ; i++)
		for (int j = 1; j <= M ; j++)
			std::cin >> maze[i][j];
}

void solve()
{
	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]}) + maze[i][j];
}

void print_val()
{
	std::cout << dp[N][M];
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}