알고리즘/L16~17 동적계획법
17. 자원 채취
쿠쿠트레인
2023. 6. 12. 10:13
문제
N x M의 지도가 주어지며, 이 지도의 각 칸에는 자원이 존재한다. 자원의 양은 정수로 나타난다. 다음 그림은 5 x 6 의 지도에 존재하는 자원을 나타낸다.
철수는 자원을 채취하는 로봇을 갖고 있으며, 이 로봇은 (0, 0) 에서 출발하여 (N-1, M-1) 에서 자원 채취를 마친다. 로봇은 한가지 제약이 있는데, 오른쪽과 아랫쪽으로밖에 움직일 수 없다는 것이다. 이 로봇을 이용하여 가장 많이 채취할 수 있는 자원의 양을 출력하는 프로그램을 작성하시오. 위의 예제의 경우 다음과 같이 채취하는 것이 최대이며, 그 양은 49이다.
입력
첫 번째 줄에 N, M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 두 번째 줄부터 N x M 의 지도에 존재하는 자원의 양이 주어진다.
출력
로봇을 이용하여 채취할 수 있는 자원의 양의 최댓값을 출력한다.
예제 입력
5 6
1 7 3 2 8 0
9 2 3 4 5 4
3 4 7 8 2 2
1 4 3 1 4 1
3 2 5 5 3 8
예제 출력
49
#include <iostream>
using namespace std;
const int MAX = 1010;
int main() {
int n,m;
int arr[MAX][MAX];
int res[MAX][MAX];
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf("%d",&arr[i][j]);
}
}
res[0][0] = arr[0][0];
for(int i=1;i<n;i++) res[i][0] = res[i-1][0] + arr[i][0];
for(int j=1;j<m;j++) res[0][j] = res[0][j-1] + arr[0][j];
for(int i=1; i<n; i++){
for(int j=1; j<m; j++){
if(res[i-1][j] > res[i][j-1]){
res[i][j] = arr[i][j]+res[i-1][j];
}else{
res[i][j] = arr[i][j]+res[i][j-1];
}
}
}
printf("%d",res[n-1][m-1]);
return 0;
}