11048번: 이동하기

메모리

시간

11048 KB

108 ms

Code

#include <cstdio>
#include <algorithm>

using namespace std;
int main()
{
	int N, M;
	scanf("%d", &N);
	scanf("%d", &M);
	int	map[1001][1001] = {0,};
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			scanf("%d", &map[i][j]);
		}
	}
	int comp = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			comp = max(map[i - 1][j], map[i][j -1]);
			map[i][j] += max(map[i - 1][j - 1],comp);
		}
	}
	printf("%d", map[N][M]);
	return 0;
}

문제풀이

움직일 수 있는 인덱스는 map[i + 1][j], map[i ][j + 1], map[i + 1][j + 1]

총 3가지 경우의 수로 이전 가능 인덱스 중 가장 큰 인덱스를 더해주며 배열을 채워갔다.