728x90
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<vector<int>> maze(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> maze[i][j];
}
}
vector<vector<int>> candy(n, vector<int>(m));
candy[0][0] = maze[0][0];
for (int i = 1; i < m; i++) {
candy[0][i] = candy[0][i - 1] + maze[0][i];
}
for (int i = 1; i < n; i++) {
candy[i][0] = candy[i - 1][0] + maze[i][0];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
candy[i][j] = max(candy[i - 1][j], candy[i][j - 1]) + maze[i][j];
}
}
cout << candy[n - 1][m - 1];
return 0;
}728x90
'알고리즘 문제' 카테고리의 다른 글
| [백준] 5598번 카이사르 암호 (0) | 2020.02.29 |
|---|---|
| [백준] 2609번 최대공약수와 최소공배수 (0) | 2020.02.29 |
| [백준] 9506번 약수들의 합 (0) | 2020.02.28 |
| [백준] 2529번 부등호 (0) | 2020.02.28 |
| [백준] 1138번 한 줄로 서기 (0) | 2020.02.28 |