문제
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; } |