[BOJ] 11048번_이동하기_DP (C++)

[문제]

https://www.acmicpc.net/problem/11048

N*M 크기의 미로가 존재하고 각 방에는 사탕이 놓여져 있다. 이 때 (1,1)에서 (N,M)으로 이동하며 방에 있는 사탕을 모두 가져갈때, 가져올 수 있는 사탕 개수의 최대값을 구하는 문제이다.

(r,c)에 존재 할때, (r+1,c), (r,c+1), (r+1,c+1)로 이동할 수 있다.

[사용 알고리즘]

DP(다이나믹 프로그래밍)

[풀이 핵심]

• (1,1)부터 (N,M)까지 2중 for문을 돌면서 현재 칸까지 오는데 가장 많은 사탕을 가져오는 개수를 저장하는 bottom-up 방식으로 답을 구하면 된다.
• 쉽게 말하면 오른쪽, 아래, 오른쪽아래(대각선)으로 밖에 이동할 수 없으므로 현재 칸까지 가장 많은 사탕을 가져오는 개수는 현재칸의 사탕개수 + 왼쪽, 위, 왼쪽위(대각선)에서 가장 많은 사탕을 가지고 있는 경우 이다.
• 점화식으로 표현하면 dp[i][j] = arr[i][j] + max(dp[i-1][j], max(dp[i][j-1], dp[i-1][j-1]))

[코드]

//boj11048번_이동하기_dp

#include<iostream>

using namespace std;

int arr[1001][1001];
int dp[1001][1001];

int main() {
	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			int num;
			cin >> num;

			arr[i][j] = num;
			dp[i][j] = num;
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			dp[i][j] = arr[i][j] + max(dp[i - 1][j], max(dp[i][j - 1], dp[i - 1][j - 1]));
		}
	}

	cout << dp[N][M];

	return 0;
}