[백준] 11048 : 이동하기

05 Jan 2021

💻

𝑫𝒚𝒏𝒂𝒎𝒊𝒄 𝑷𝒓𝒐𝒈𝒓𝒂𝒎𝒎𝒊𝒏𝒈

𝑷𝒓𝒐𝒃𝒍𝒆𝒎

(1,1)에서 (N,M)까지 (r+1,c), (r,c+1), (r+1,c+1)으로만 이동하여 구할 수 있는 최대 합은?

𝑺𝒐𝒍𝒗𝒆

일정 크기의 작은 범위 내에서의 풀이가, (범위+1), (범위+2), … 까지의 풀이에 모두 통하는 경우에 다이나믹 프로그래밍을 사용합니다.
해당 문제의 경우, (1,1)이 아닌 어떤 모든 좌표에 도달하기까지 가질 수 있는 사탕의 최대 갯수는 {현재 좌표의 사탕 갯수} + max( {(r-1,c)의 사탕갯수}, {(r,c-1)의 사탕갯수}), {(r-1,c-1)의 사탕갯수} ) 입니다.

𝑪𝒐𝒅𝒆

/*
11048 이동하기
풀이 :
	(1,1)에서 (N,M)까지 이동할 때 가져올 수 있는 사탕 갯수의 최대값
	단, 준규는 (x+1,y), (x,y+1), (x+1,y+1)로만 이동할 수 있다.
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
int dir[3][2] = { {-1,0},{0,-1},{-1,-1} };

bool isValidate(int x, int y)
{
	return (x >= 0) && (y >= 0);
}
int main()
{
	int map[1001][1001];
	int DP[1001][1001];

	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			map[i][j] = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {

			if (i == 0 && j == 0) {
				cin >> map[0][0];
				DP[0][0] = map[0][0];
				continue;
			}

			cin >> map[i][j];

			int max_v = 0;
			for (int d = 0; d < 3; d++) {
				int next_x = j + dir[d][0];
				int next_y = i + dir[d][1];
				if (isValidate(next_y, next_x)) {
					max_v = max(max_v, DP[next_y][next_x]);
				}
			}
			DP[i][j] = map[i][j] + max_v;
		}
	}

	cout << DP[N - 1][M - 1];
	return 0;

}