/ 알고리즘

자원채취

알고리즘 dp scv 동적프로그래밍 자원채취
https://4am.kr/-ec-9e-90-ec-9b-90-ec-b1-84-ec-b7-a8/

프로그램 명: scv

제한시간: 1 초
  ![scv](/content/images/2016/09/scv.gif)

N * N 크기의 맵이 있다. 이 맵에는 미네랄이 군데군데 매장되어 있어서 당신은 SCV 를 이용해 이 미네랄을 채취하려고 한다.

SCV 는 (1,1) 의 위치에서 출발하여 (N,N)까지 이동하는데, 이 SCV 는 고물이라 오른쪽 또는 아래쪽으로 밖에 움직이지 못한다. 이 SCV 는 무한한 양의 미네랄을 가지고 있을 수 있다고 가정하자. 이 SCV 를 이용해서 최대한 많이 미네랄을 얻도록 하는 프로그램을 작성하시오.

입력 방법

  • 첫 줄에는 맵의 크기 N ( 3 <= N <= 100)이 주어진다.
  • 둘째줄부터는 주어진 지도가 N 줄 만큼 입력된다. (단, 0 은 미네랄 없음, 1 은 미네랄 있음을 의미한다.)

출력 방법

SCV 가 채취할 수 있는 최대 미네랄 양을 출력한다.

입출력 예

입력
5
0 1 0 0 1
0 0 1 0 0
1 0 1 1 0
1 1 0 1 0
1 0 0 0 1
출력
6

나의 풀이

#include <iostream>
using namespace std;
int main()
{
    int n, mmap[102][102], rmap[102][102];
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 6; j++)
            mmap[i][j] = rmap[i][j] = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> mmap[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (rmap[i - 1][j] >= rmap[i][j - 1])
                rmap[i][j] = mmap[i][j] + rmap[i - 1][j];
            else if (rmap[i - 1][j] < rmap[i][j - 1])
                rmap[i][j] = mmap[i][j] + rmap[i][j - 1];
        }
    cout << rmap[n][n] << endl;
    return 0;
}