[백준 14430] 자원 캐기 (C++)

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

문제

---

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

 

입력

---

첫째 줄에 WOOK이 탐사할 영역의 세로길이 N(1 ≤ N ≤ 300)과 가로길이 M(1 ≤ M ≤ 300)이 주어진다. 그 다음 N행 M열에 걸쳐 탐사영역에 대한 정보가 주어진다. 숫자는 공백으로 구분된다. (자원은 1, 빈 땅은 0으로 표시된다)

 

출력

---

WOOK이 수집할 수 있는 최대 광석의 개수를 출력하라.

 

문제 풀이

---

dp 기본 문제.

 

오른쪽 혹은 아래로만 이동할 수 있기 때문에 특정 칸에 도달했다면 해당 칸 위쪽에서 오거나, 해당 칸 왼쪽에서 와야 한다. 위쪽에서 왔다면 해당 칸까지 채취한 자원은 위쪽 칸까지 채취한 자원 + 현재 칸에서 채취한 자원이다. 왼쪽에서 왔다면 해당 칸까지 채취한 자원은 왼쪽 칸까지 채취한 자원 + 현재 칸에서 채취한 자원이다. 두 값을 비교하여 큰 값을 선택하면 해당 칸으로부터 얻을 수 있는 최댓값을 얻을 수 있다.

 

아래는 코드.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	int** arr = new int*[N];
	int** dp = new int*[N];
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[M];
		dp[i] = new int[M];
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
		}
	}
	dp[0][0] = arr[0][0];
	for (int i = 1; i < N; i++)
	{
		dp[i][0] = dp[i - 1][0]+arr[i][0];
	}
	for (int i = 1; i < M; i++)
	{
		dp[0][i] = dp[0][i - 1] + arr[0][i];
	}
	for (int i = 1; i < N; i++)
	{
		for (int j = 1; j < M; j++)
		{
			dp[i][j] = max(dp[i - 1][j], dp[i][j-1]) + arr[i][j];
		}
	}
	cout << dp[N - 1][M - 1] << "\n";
	return 0;
}