[성실코딩 6일차] 백준 #11048 이동하기 / DP

내가 아는 DP 2차원 map 문제 중에서 가장 전형적인 문제

얏호 처음으로 DP풀었당

예제 입출력 1번 풀이방법

#include<iostream>

using namespace std;

int map[1001][1001] = { 0, };
int DP[1001][1001] = { 0, };

int dx[3] = { 0,1,1 }; //하,우하대각선,우
int dy[3] = { 1,1,0 };

int main(void) {

	int n, m;

	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}

	DP[0][0] = map[0][0];

	// map n,m 모두 방문하기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			// (i,j)에서 가능한 방향 3가지.
			for (int k = 0; k < 3; k++) {
				if ( ( i+dy[k]<0 || i+dy[k]>n-1 ) ||
					( j+dx[k]<0 || j+dx[k]>m-1) ) { // x,y 범위가 map을 벗어나면 pass
					continue;
				}
				else {
					int temp = DP[i][j] + map[i+dy[k]][j+dx[k]];
					if (DP[i + dy[k]][j + dx[k]] < temp) {
						// update
						DP[i + dy[k]][j + dx[k]] = temp;
					}
				}
			}
		}
	}
	
	cout << DP[n-1][m-1] << endl;

	return 0;
}