문해기 과제 3

과제 3: 동전 모으기

N x M 크기의 네모칸들이 있다. 각 칸에는 0개 이상 100개 이하의 동전이 있다.

이제 가장 왼쪽 위 네모칸에서, 가장 오른쪽 아래 네모칸으로 이동하려고 한다. 이동할 때는 바로 오른쪽 옆 네모칸, 또는 바로 아래 네모칸으로만 이동할 수 있다.

예를 들어 아래와 같이 4 x 5 크기 네모칸을 생각해보자. 숫자는 각 칸에 있는 동전의 개수이다.


0 4 0 2 0

1 2 0 0 1

1 0 3 0 0

2 1 2 4 2

가장 왼쪽 위에 있는 0개의 동전이 있는 칸에서, 가장 오른쪽 아래에 있는 2번 동전이 있는 칸으로 위 규칙을 지키면서 이동하려 한다. 예를 들어, 0 - 4 - 2 - 0 - 3 - 2 - 4 - 2로 이동하면 총 17개의 동전을 얻을 수 있다.

이 과정에서 얻을 수 있는 동전의 총 합 중 가장 작은 값을 구하는 프로그램을 작성하시오. 위의 예에서는 5가 가장 작은 값이다.

입력

입력은 다음과 같이 이루어진다. 첫 줄에는 두 자연수 N, M이 주어지며, 이는 네모칸의 크기를 나타낸다. N, M 모두 1 이상 1,000 이하이다.

다음 N 줄에는 한 줄에 총 M개의 0 이상 100 이하의 정수가 주어지는데, 이는 해당하는 줄의 각 칸에 있는 동전의 개수를 의미한다.


출력

단 하나의 정수를 출력하며, 이는 입력받은 네모칸을 주어진 조건대로 이동했을 때 얻을 수 있는 동전의 개수의 총합 최소값이다.


입력 예제

4 5

0 4 0 2 0

1 2 0 0 1

1 0 3 0 0

2 1 2 4 2

출력 예제

5

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

void make_ans(ll start_x, ll start_y, ll end_x, ll end_y, vector<vector<ll>>& ans, vector<vector<ll>> input) {
    if (start_x == end_x && start_y == end_y) {
        ans[start_y][start_x] = input[start_y][start_x] + min(ans[start_y][start_x - 1], ans[start_y - 1][start_x]);
        return;
    }
    if (start_x == 0 && start_y == 0) {
        ans[start_y][start_x] = input[start_y][start_x];
        if (start_x + 1 <= end_x) make_ans(start_x + 1, start_y, end_x, end_y, ans, input);
        if (start_y + 1 <= end_y) make_ans(start_x, start_y + 1, end_x, end_y, ans, input);
        return;
    }
    if (start_x == 0) {
        ans[start_y][start_x] = input[start_y][start_x] + ans[start_y - 1][start_x];
        if (start_x + 1 <= end_x) make_ans(start_x + 1, start_y, end_x, end_y, ans, input);
        if (start_y + 1 <= end_y) make_ans(start_x, start_y + 1, end_x, end_y, ans, input);
        return;
    }
    if (start_y == 0) {
        ans[start_y][start_x] = input[start_y][start_x] + ans[start_y][start_x-1];
        if (start_x + 1 <= end_x) make_ans(start_x + 1, start_y, end_x, end_y, ans, input);
        if (start_y + 1 <= end_y) make_ans(start_x, start_y + 1, end_x, end_y, ans, input);
        return;
    }
    ans[start_y][start_x] = input[start_y][start_x] + min(ans[start_y][start_x - 1], ans[start_y - 1][start_x]);
    if (start_x + 1 <= end_x) make_ans(start_x + 1, start_y, end_x, end_y, ans, input);
    if (start_y + 1 <= end_y) make_ans(start_x, start_y + 1, end_x, end_y, ans, input);
    return;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll N, M;
    cin >> N >> M;
    vector<vector<ll>> arr;
    vector<vector<ll>> ans;
    for (ll i = 0; i < N; i++) {
        vector<ll> tmp;
        vector<ll> tmp_a;
        for (ll j = 0; j < M; j++) {
            ll input;
            cin >> input;
            tmp.push_back(input);
            tmp_a.push_back(INT_MAX);
        }
        arr.push_back(tmp);
        ans.push_back(tmp_a);
    }
    make_ans(0, 0, M - 1, N - 1, ans, arr);
    cout << ans[N-1][M-1];

    return 0;
}