[백준 14430번] 자원 캐기

[백준 14430번] 자원 캐기

www.acmicpc.net/problem/14430

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이 수집할 수 있는 최대 광석의 개수를 출력하라.

 

 

 풀이

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int N, M;
	int arr[300][300]={0,};
	int dp[300][300]={0,};
	
	cin >> N >> M;
	for(int i=0;i<N;i++){
		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 j=1;j<M;j++) dp[0][j] = dp[0][j-1] + arr[0][j];
	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];
	return 0;
}

 처음에 생각도 별로 안하고 BFS로 접근했다가 메모리초과를 받았다. 방문체크 없이 나가기 때문에 O(2^N)으로 BFS로는 풀 수가 없다. DP가 올바른 접근인데 문제에서 왼쪽 위부터 시작하여 오른쪽 아래로 도달할 때까지 이동하는 방법이 오른쪽으로 가거나 아래로만 갈 수 있기 때문에 DP로 풀 수 있다. 제일 윗 줄과 왼쪽 줄의 값을 먼저 구해 준뒤 특정 위치의 값을 구할 때 왼쪽 값과 윗쪽 값을 비교하여 큰 것을 고르는 식으로 풀면 된다.