본문 바로가기

개발/알고리즘

폐지줍기

문제


N×N 격자로 이루어진 도시가 있다. 이 도시 군데군데에는 폐지가 버려져 있다.


범수는 가장 왼쪽 위 격자 (1, 1)에서 출발하여 가장 오른쪽 아래 격자 (N, N)까지 이동하며 폐지를 줍는데, 최단 경로를 따라가야만 한다. 즉, 인접한 오른쪽 칸 또는 아래쪽 칸으로만 이동할 수 있다. 이 때, 범수가 수집할 수 있는 폐지의 최대값을 출력하시오.


출발점과 도착점에 위치한 폐지 또한 주울 수 있다.




입력


첫 번째 줄에는 도시의 크기 N이 주어진다. (2 ≤ N ≤ 200)


두 번째 줄부터 N개의 줄에 걸쳐 도시의 정보가 주어진다. 도시의 정보 중 i번째 줄의 j번째 숫자는 격자 (i, j)에 버려진 폐지의 양 A_ij을 나타낸다. (0 ≤ A_ij ≤ 1000)




출력


범수가 주울 수 있는 최대 폐지 양을 출력한다.




힌트


예제 입력


4

1 0 1 7

2 0 2 0

0 2 2 1

1 3 3 2


예제 출력


13





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
#include <iostream>
#include <fstream>
  
  
using namespace std;
long long D[201][201];
int N;
long long M[201][201];
  
int main() {
    //ifstream cin("input.txt");
    cin >> N;
  
    for (int i = 0; i <= N; i++) {
        M[i][0] = 0;
        M[0][i] = 0;
    }
  
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> M[i][j];
            if (i == 1) {
                D[1][j] = M[i][j] + D[i][j-1];
            }
            else if (j == 1) {
                D[i][1] = M[i][j] + D[i-1][j];
            }
            else {
                if (D[i - 1][j] > D[i][j - 1]) {
                    D[i][j] = M[i][j] + D[i - 1][j];
                }
                else {
                    D[i][j] = M[i][j] + D[i][j - 1];
                }
            }
        }
    }
    //BFS();
    cout << D[N][N] << endl;
    //system("pause");
    return 0;
}


'개발 > 알고리즘' 카테고리의 다른 글

일방통행  (0) 2017.01.15
마트료시카  (0) 2016.12.09
합분해  (0) 2016.12.09
롤러코스터  (0) 2016.12.09
인접한 비트의 개수  (0) 2016.12.09