[11048] 이동하기(C++/DP)

1. 문제

www.acmicpc.net/problem/11048

11048번: 이동하기

2. 접근 방법

1) 이동방향이 (r+1, c), (r, c+1), (r+1, c+1) 이므로 사이클은 생기지 않는다. (1,1)->(N,M)까지 갈 수 있는 경우의 수를 구하려고 했다.

 

2) candy[i][j]가 (i,j)번째 도착했을 때 얻을 수 있는 최대 사탕 개수라고 할 때, candy[i][j]는 미로의 (i,j)번째 방에 놓인 사탕의 수 + (i,j)에 오기 직전까지 가장 많이 얻을 수 있는 사탕의 개수이다. 이 때,(i,j)에 올 수 있는 경우의 수는 (i-1,j)에서 오는 경우, (i,j-1)에서 오는 경우, (i-1,j-1)에서 오는 경우 총 3가지 이다. 이를 수식으로 표현하면

candy[i][j] = map[i][j] + max({candy[i][j-1],candy[i-1][j], candy[i-1][j-1]})이다.

 

3) top-down방식으로 (N-1,M-1)에서 시작해서 (0,0)까지 재귀 함수를 돌릴 수 있다. 이 때 memorization을 사용하여 한번 구한 candy[i][j]값은 값으로 저장해두면 효율적이다.

 

3) 사실 top-down방식은 쉬운데, bottom-up으로 생각하기 어려웠다. 그런데 나중에 이동 방향을 다시 생각해보니 우측, 아래측, 우측하단(대각선)이므로 2중 for문의 방향과 일치했다..!! 그래서 이번 문제의 경우는 bottom-up으로도 같은 수식으로 문제를 풀 수 있다.. 대신 이동 방향이 사방으로 펼쳐져있으면 bottom-up으로 풀면 안된다..!! 조심!!

 

3. 실수했던 부분 & 처음 알았던 부분

1) 2차원 벡터를 전역변수로 선언하고, main에서 (N,M)만큼 메모리 할당하는 법

: vector<int> tmp(M,0);

  v.assign(N,tmp);

  

2) 이동 방향이 (오른쪽, 아래쪽, 오른쪽아래) 3개가 있으면 bottom-up으로도 쉽게 풀 수 있다.

4. 코드

/*
candy[i][j] : (i,j)에 도착했을 때 가질 수 있는 사탕 개수의 최대값
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N,M;
vector<vector<int> > map(1000,vector<int>(1000,0));
vector<vector<int> > candy(1000,vector<int>(1000,-1));

int go( int x,int y) {

	if( x< 0 || y < 0 ) return 0;
	if(candy[x][y] != -1) return candy[x][y];
	
	candy[x][y] = map[x][y] + max({go(x-1,y),go(x-1,y-1),go(x,y-1)});
	return candy[x][y];
}

int main() {
	cin >> N >> M;	
	
	for(int i=0;i<N;i++)
	 for(int j=0;j<M;j++)
	  	cin >> map[i][j];

	cout << go(N-1,M-1) <<endl;
	return 0;
}