💻
𝑫𝒚𝒏𝒂𝒎𝒊𝒄 𝑷𝒓𝒐𝒈𝒓𝒂𝒎𝒎𝒊𝒏𝒈
𝑷𝒓𝒐𝒃𝒍𝒆𝒎
(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;
}