알고리즘/Backjoon

[C++] 11048 - 이동하기

ShinDongJun 2019. 12. 7. 20:47

문제 링크 : https://www.acmicpc.net/problem/11048

 

11048번: 이동하기

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으

www.acmicpc.net

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<algorithm>
#define MAX(A, B) (A > B ? A : B)
#define endl '\n'
 
using namespace std;
 
int M[1005][1005];
 
int main(void)
{
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int k;
    int n, m; cin >> n >> m;
 
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            cin >> k;
            M[i][j] = k;
            if(i == 0 && j > 0)
                M[i][j] += M[i][j-1];
            if(j == 0 && i > 0)
                M[i][j] += M[i-1][j];
            if(i > 0 && j > 0)
                M[i][j] += MAX(M[i][j-1], M[i-1][j]);
        }
    }
 
    // for(int i = 0; i < n; ++i)
    // {
    //     for(int j = 0; j < m; ++j)
    //     {
    //         cout << M[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
 
    cout << M[n-1][m-1] << endl;
 
    return 0;
}