백준 - 11048번 이동하기

문제

사탕을 가져오면서 아래로 한 칸, 우측으로 한 칸 씩 길을 지나갈 때,
최대로 가져올 수 있는 사탕 개수는?

생각

모든 길을 다 다녀와봐야, 가져올 수 있는 사탕 최대 개수를 알 수 있으니까! BF 문제인가?

DP는 모든걸 다 해본다는 건데, 그러면 너무 계산양도 많고 오래걸리니까
중간에 알아낸 정보들을 저장하고, 다른 곳 정보를 구할 때 사용하는 방법! DP로 풀어보자~

저장된 정보들을 사용하는 점화식을 세워서 우리가 원하는 값을 알아보자!
어느 한 위치에 도착했을 때 가장 많은 사탕을 가지고 있는 법은
가장 많은 사탕을 가진 경로로 부터 오면 된다

즉, 위 또는 옆에서 올 때 더 많은 사탕을 가진 경로를 택하면 됨

candy[i][j] = candy[i][j] + max(candy[i - 1][j], candy[i][j - 1]);

대각선으로도 이동할 수 있긴한데, 사탕개수가 양수니까
대각선으로 올빠엔 꺽어서 옆 아래 혹은 아래 옆 으로 오는게 더 많이 사탕이 있겠지?
그러니까 위에서 오거나, 옆에서 온 거만 봐줘도 될 듯~!~!

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

int n, m;
int candy[1005][1005];

int findMaxCandy() {

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int case1 = candy[i - 1][j];
			int case2 = candy[i][j - 1];
			candy[i][j] = candy[i][j] + max(case1, case2);
		}
	}

	return candy[n][m];
}

int main() {
	cin >> n >> m;

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

	cout << findMaxCandy();

	return 0;
}