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

문제링크 : https://www.acmicpc.net/problem/14430

14430번: 자원 캐기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M;
int arr[301][301], dp[301][301];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            cin >> arr[i][j];
        }
    }

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            dp[i][j] = max({dp[i][j], dp[i-1][j] + (arr[i][j]==1), dp[i][j-1] + (arr[i][j]==1)}); //위->아래, 왼쪽->오른쪽 + 자원 여부 확인
        }
    }

    cout << dp[N][M];
    return 0;
}

 

이동방향이 위->아래 / 왼쪽 -> 오른쪽 이렇게 2가지이다.

따라서 현재값, 위->아래 + 자원유무, 왼쪽->오른쪽 + 자원유무 중 가장 큰 값을 골라서 dp에 저장한다.

 

자원의 경우 있으면 1 없으면 0을 담아야 하므로 (arr[i][j]==1)을 통해 자원 유무를 체크하여 더해주도록 했다.

(1인 경우가 있는 경우)