백준/DP
(c++)백준 11048번: 이동하기
Nimgnoej
2020. 9. 13. 16:29
11048번: 이동하기
준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 ��
www.acmicpc.net
[풀이]
진행할수록 범위가 좁아지므로 DP를 사용한다.
어느 방향에서 와야 값이 커지는 지 확인
점화식
DP[i][j] = Maze[i][j] + max(DP[i-1][j], max(DP[i][j-1], DP[i-1][j-1]))
#include <iostream>
#include <algorithm>//max
using namespace std;
int N, M;
int Maze[1001][1001];
int DP[1001][1001];
void solution() {
DP[1][1] = Maze[1][1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
DP[i][j] = Maze[i][j] + max(DP[i - 1][j], max(DP[i][j - 1], DP[i - 1][j - 1]));
}
}
cout << DP[N][M] << '\n';
}
int main() {
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> Maze[i][j];
}
}
solution();
}