(c++)백준 11048번: 이동하기

www.acmicpc.net/problem/11048

11048번: 이동하기

[풀이]

진행할수록 범위가 좁아지므로 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();
}