[C/C++] 백준 - 14430번 : 자원 캐기

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

14430번: 자원 캐기

문제

인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. WOOK은 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있으며, 그 외의 방향으로 움직이는 것은 불가능하다. WOOK은 자신이 위치한 (x, y)에 자원이 있는 경우에만 해당 자원을 채취할 수 있다. WOOK이 탐사할 영역에 대한 정보가 주어질 때, WOOK이 탐색할 수 있는 자원의 최대 숫자를 구해라!

 

 

갈 수 있는 경로는 2가지로 정해져있고, 모든 경우를 확인해야한다.

하지만 모든 경우의 수를 확인한다고 매 번 같은 작업을 반복한다면 시간도 오래걸리고 매우 비효율적이기 때문에

메모이제이션을 적용하여 시간을 단축한다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000007
#define endl '\n'

using namespace std;

int N, M;
int cache[303][303];
int board[303][303];

void input() {
	cin >> N >> M;
	memset(cache, -1, sizeof(cache));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> board[i][j];
		}
	}
}

bool isValid(int y, int x) {
	return (1 <= y && y <= N && 1 <= x && x <= M);
}

int solution(int y, int x) {
	if (y == N && x == M) return board[y][x];
	if (!isValid(y, x)) return 0;
	int& ret = cache[y][x];
	if (ret != -1) return ret;
	ret = 0;
	ret = max(solution(y + 1, x), solution(y, x + 1)) + board[y][x];
	return ret;
}

int main() {
	fastio;
	input();
	cout << solution(1, 1) << endl;

	return 0;
}