11048번 : 이동하기

모든 수를 담을 공간이 1000x1000이고, 이는 이차원 배열로 충분히 들어가기 때문에 dp도 1000x1000으로 정의해도 괜찮다.

방법은 간단하다. 배열을 arr에 모두 받은 다음 dp[i][j]가 dp[i-1][j] , dp[i][j-1] , dp[i-1][j-1] 중 가장 큰 값 + arr[i][j]으로 쌓아주면 된다.

#include <stdio.h>

int dp[1001][1001], arr[1001][1001], N, M;

int MAX3(int a, int b, int c) {

return a > (b > c ? b : c) ? a : (b > c ? b : c);

}

int main() {

scanf("%d %d", &N, &M);

for (int i = 1; i <= N; ++i) {

for (int j = 1; j <= M; ++j) {

scanf("%d", &arr[i][j]);

}

}

dp[0][0] = 0;

for (int i = 1; i <= N; ++i) {

for (int j = 1; j <= M; ++j) {

dp[i][j] = MAX3(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + arr[i][j];

}

}

printf("%d", dp[N][M]);

}