[BOJ/Silver 2] 백준 14430 자원 캐기(C++)

문제 링크

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

 

문제

인류의 차세대 인공지능 자원 캐기 로봇인 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이 수집할 수 있는 최대 광석의 개수를 출력하라.

 

예제 입력 1

5 4
0 1 0 0
0 0 1 0
1 1 0 0
1 0 1 0
1 1 0 0

예제 출력 1

4

 

알고리즘 분류

• 다이나믹 프로그래밍

 

풀이

(i, j) 칸까지 왔다고 하자.

현재 칸까지 오는 방법은 (i - 1, j), 그리고 (i, j - 1) 칸에서 한 칸 이동하는 2가지의 수밖에 없다.

따라서 현재 칸까지 왔을 때 캔 자원의 개수의 최댓값은 (i - 1, j)에서 캔 자원의 개수와 (i, j - 1)에서 캔 자원의 개수 중 최댓값이며, 현재 칸에 자원이 존재하는 경우 1을 더하면 된다.

해당 칸까지 왔을 때 캘 수 있는 자원의 최댓값을 (1, 1)에서부터 시작해서 (N, M)까지 도달할 때까지 기록해둔다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 301
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
int MAP[MAX][MAX];
int DP[MAX][MAX];

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

void settings() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]) + MAP[i][j];
        }
    }
}

void find_Answer() {
    cout << DP[N][M] << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}