11048번 이동하기

문제풀이

전형적인 DP의 최적의 원리가 보이는 문제이다.

DP풀이

결국 정답은 최적의 루트의 합일수 밖에없으므로
x,y블록으로 가기까지 얻을수 있는 최대 점수는 그전블록의 최대점수와 관련이 깊다.

점화식

1. 문제에서 이동방향은 3가지로 한정된다. 동, 남, 동남
2. dp[n][m] = a, (n,m)으로 갈때 얻을 수 있는 최대 점수 a 를 뜻한다.
3. 가장자리, 즉 n=1이거나 m=1일때는 동쪽 또는 남쪽으로 밖에 움직일 수 없으므로 따로 처리해줘야 한다.
4. 가장자리는 어차피 한방향이므로 그길에 있는 점수들을 모두 더하면된다.

   처음에 3번과 4번을 간과해서 틀렸다가 반례를 보고 찾았다 참고

코드

#define MAX 1000+2

int N,M;
int dp[MAX][MAX];
int answer;
int Map[MAX][MAX];

int threeMax(int a, int b, int c)
{

	int tmp;
	tmp = max(a, b);
	tmp = max(tmp, c);

	return tmp;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");


	cin >> N>>M;

	
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin>>Map[i][j];
		}
	}

	dp[1][1] = Map[1][1];

	for (int i = 2; i <= M; i++)
	{
		dp[1][i] = dp[1][i - 1] + Map[1][i];
	}
	for (int i = 2; i <= N; i++)
	{
		dp[i][1] = dp[i - 1][1] + Map[i][1];
	}

	for (int i = 2; i <= N; i++)
	{
		for (int j = 2; j <= M; j++)
		{
			dp[i][j] = threeMax(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
			dp[i][j] += Map[i][j];
		}
	}a
	
	cout << dp[N][M];
}