백준 BOJ 14430 - 자원 캐기

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

14430번: 자원 캐기

 

DP로 해결했던 문제

 

DP[i][j] 를 $(i,j)$ 까지 이동해서 채취할 수 있는 최대 자원 으로 정의한다. 

$(i,j)$ 로 이동하는 경우는

1.  $(i-1,j)$ 에서 이동한 경우
2.  $(i,j-1)$ 에서 이동한 경우
   

 

두가지 경우가 있으므로,

DP[i][j] = MAX( DP[i-1][j], DP[i][j-1] ) + arr[i][j]

로 계산해주면 정답을 얻을 수 있다.

 

DP의 정의에 따라 정답은 DP[N][M]

#include <bits/stdc++.h>
using namespace std;

int arr[345][345] = {0};
int dp[345][345] = {0};

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