PS/BOJ

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

도비(Doby) 2022. 11. 5. 22:06

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

 

14430번: 자원 캐기

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

www.acmicpc.net

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;
}