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

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

14430번: 자원 캐기

---

Solved By: DP

 

간단한 점화식으로 구성됩니다.

현재 좌표값이 1일 경우

cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]) + 1

현재 좌표값이 0일 경우

cache[i][j] = max(cache[i - 1][j], cache[i][j - 1])

#include <iostream>
#define MAX 301
using namespace std;

int N, M;

int wook[MAX][MAX];
int cache[MAX][MAX];

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