백준 11048번: 이동하기

[문제 링크]

11048번: 이동하기

---

간단한 dp문제였다.

 

이동할수 있는 방향이 (y+1, x), (y, x+1), (y+1, x+1) 세가지 존재하기 때문에 (N, M)까지 이동할 때 얻을 수 있는 사탕 개수의 최댓값은 (N, M) 이전에 위치할 수 있는 좌표들 중 최댓값을 선택하도록 구현하면 원하는 결과를 얻을 수 있다.

 

추가) 좌표에 존재하는 사탕개수가 0 이상이기 때문에 대각선으로 이동하는 것보다 왼쪽 또는 아래로 이동하는 것이 항상 이득이다. 따라서 대각선으로 이동하는 (y+1, x+1) 의 경우는 고려하지 않아도 된다.

---

#include <iostream>
#include <cstring>
using namespace std;

int arr[1001][1001], memo[1001][1001];

inline int max(int a, int b) { return a > b ? a : b; }

int Topdown(int y, int x)
{
	if (y == 0 || x == 0)
		return 0;

	int& ret = memo[y][x];
	if (ret != -1) return ret;

	return ret = max(Topdown(y - 1, x), max(Topdown(y, x - 1), Topdown(y - 1, x - 1))) + arr[y][x];
}

int Bottomup(int N, int M)
{
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			memo[i][j] = max(memo[i - 1][j], max(memo[i][j - 1], memo[i - 1][j - 1])) + arr[i][j];

	return memo[N][M];
}

int main(void)
{
	int N, M;
	cin >> N >> M;

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

	memset(memo, -1, sizeof(memo));
	cout << Topdown(N, M) << endl;
	
	memset(memo, 0, sizeof(memo));
	cout << Bottomup(N, M) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 83 day