Search
Duplicate
🙆🏻‍♀️

이동하기

주차
13
문제번호
11048
언어
티어
실버
유형
DP
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

메모리

시간

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가지 경우의 수로 이전 가능 인덱스 중 가장 큰 인덱스를 더해주며 배열을 채워갔다.