[Day 1] 이동하기

우연히도 같은날 랜덤으로 뽑은 문제가, DP 였다.

이번에는 1차원 배열속에서가 아닌 2차원배열속에서의 DP를 구하는 문제이다.

백준 11048 문제이고,

N * M 배열에서 (1,1)에서 출발하여 (N,M)에 도착할때까지 사탕의 개수가 최대로 출력되야한다.

그림으로 그려보면 방향은 

(1,1) 에서 세방향으로 이동할 수 있으며, 이동하기 전에 현재위치에 올 값을 현재위치 x,y 좌표에 대해 둘다 바로 직전값, 각각의 x,y 좌표에 대해 직전값에 대해 생각해볼 수 있다.

따라서 위의 미로에서의 최대 값이 나오기 위해서는 경로가 아래와 같이 이동해야한다.

<소스코드>

#include <cstdio>
#include <algorithm>
using namespace std;
int dp[1001][1001],N,M,num[1001][1001];

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%d", &num[i][j]);
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (i <= 0 || j <= 0) continue;
			dp[i][j] = max(dp[i - 1][j - 1], max(dp[i][j - 1], dp[i - 1][j])) + num[i][j];
		}
	}
	printf("%d\n", dp[N][M]);
	return 0;
}