문제
https://www.acmicpc.net/problem/11048
문제해설
미로가 주어지고 각 방에는 사탕이 하나씩 놓여있다.
준규는 미로안에서 오른쪽, 아래, 오른쪽 아래 대각선 방향으로만 움직일 수 있다.
n, m 크기의 미로에서 가장 오른쪽 아래 방에 도착했을 때
얻을 수 있는 최대의 사탕 개수를 구하면 된다.
문제풀이
n, m 행렬을 만들고 사탕 개수를 입력받는다.
2중 반복문을 돌면서 위, 왼쪽, 왼쪽 위 대각선을 보며
가장 큰 수를 자신과 더하는 방식으로 탐색하면 된다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int arr[1001][1001];
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> arr[i][j];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
arr[i][j] += max(max(arr[i - 1][j], arr[i][j - 1]), arr[i - 1][j - 1]);
}
}
cout << arr[n][m];
return 0;
}