메모리
시간
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;
}
C++
복사
문제풀이
움직일 수 있는 인덱스는 map[i + 1][j], map[i ][j + 1], map[i + 1][j + 1]
총 3가지 경우의 수로 이전 가능 인덱스 중 가장 큰 인덱스를 더해주며 배열을 채워갔다.