하루하루 꾸준히, 인생은 되는대로

알고리즘

백준 14430 자원 캐기 C++

긤효중 2022. 5. 9. 19:34

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

 

14430번: 자원 캐기

인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다.

www.acmicpc.net


문제

인류의 차세대 인공지능 자원 캐기 로봇인 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>
//백준 14430 자원캐기
using namespace std;
int max(int a,int b){
    if(a>b){
        return a;
    }
    else{
        return b;
    }
}
int main(void){
    int arr[301][301];
    int dp[301][301];
    int n,m;
    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 = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(j == 0){
                dp[i][j] = dp[i-1][j] + arr[i][j];
            }
            else{
                dp[i][j] = max((dp[i][j-1] + arr[i][j]),(dp[i-1][j] + arr[i][j]));
            }
        }
    }
    cout << dp[n-1][m-1];
 
}