[백준]11048번: 이동하기

https://www.acmicpc.net/problem/11048

11048번: 이동하기

---

너무 BFS 문제처럼 생겼지만 bfs로 풀면 메모리 초과가 난다

이 문제는 한 칸으로부터 이동할 수 있는 칸이 최대 3개로 제한되어 있고, 최단 거리를 구하는 문제도 아니기 때문에 dp로 풀면 댄다

dp문제인걸 알고 풀면 아주 쉽다

 

 

첫번째 예제를 가지고 풀어보자

 

배열을 2개 만들어준다. maze에는 놓여있는 사탕 수를, dp에는 획득한 사탕 수의 최대를 저장할거다

 

한 칸씩 이동하면서 기존보다 더 많은 사탕을 얻을 수 있게 되면 dp 값을 갱신해줄거임

 

---

한 칸씩 순서대로 해보면 이렇게 된당

 

현재까지 획득한 사탕 수 (dp[현재칸]) + 다음 칸으로 이동시 추가로 획득할 사탕 수 (maze[다음칸]) 의 값이 dp[다음칸] 보다 큰 경우에만 갱신

 

배열이 작으니까 끝까지 쭉 하나씩 해보면

 

 

---

#include <iostream>
using namespace std;

int main(){

	int n,m; cin>>n>>m;
	int maze[n][m], DP[n][m];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			int x; cin>>x;
			maze[i][j]=x; DP[i][j]=x;
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(i+1<n && DP[i][j]+maze[i+1][j] > DP[i+1][j]) DP[i+1][j]=DP[i][j]+maze[i+1][j];
			if(i+1<n && j+1<m && DP[i][j]+maze[i+1][j+1] > DP[i+1][j+1]) DP[i+1][j+1]=DP[i][j]+maze[i+1][j+1];
			if(j+1<m && DP[i][j]+maze[i][j+1]>DP[i][j+1]) DP[i][j+1]=DP[i][j]+maze[i][j+1];
		}		
	}
	cout<<DP[n-1][m-1];
	return 0;
}