SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다.
아래는 N=5 의 예이다.
M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다.
죽은 파리의 개수를 구하라!
예를 들어 M=2 일 경우 위 예제의 정답은 49마리가 된다.
[제약 사항]
1. N 은 5 이상 15 이하이다.
2. M은 2 이상 N 이하이다.
3. 각 영역의 파리 갯수는 30 이하 이다.
[입력]
가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,
다음 N 줄에 걸쳐 N x N 배열이 주어진다.
[출력]
출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.
(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)
입력10
5 2
1 3 3 6 7
8 13 9 12 8
4 16 11 12 6
2 4 1 23 2
9 13 4 7 3
6 3
29 21 26 9 5 8
21 19 8 0 21 19
9 24 2 11 4 24
19 29 1 0 21 19
10 29 6 18 4 3
29 11 15 3 3 29
...
5 2
1 3 3 6 7
8 13 9 12 8
4 16 11 12 6
2 4 1 23 2
9 13 4 7 3
6 3
29 21 26 9 5 8
21 19 8 0 21 19
9 24 2 11 4 24
19 29 1 0 21 19
10 29 6 18 4 3
29 11 15 3 3 29
...
누적합인가 했는데 생각안나서 4중 for문을..
#include <iostream>
#include <vector>
using namespace std;
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int test_case;
cin >> test_case;
for(int t = 1; t <= test_case; t++){
int n, m;
cin >> n >> m;
vector<vector<int>> arr(n,vector<int>(n,0));
for(int i =0; i < n; i++){
for(int j = 0; j < n; j++){
int tmp;
cin >> tmp;
arr[i][j] = tmp;
}
}
int max = -1;
int tmp = 0;
for(int i =0; i <= n - m; i++){
for(int j = 0; j <= n - m; j++){
//여기부터 파리채로 때린 넓이 구하기
tmp = 0;
for(int k = i; k < i + m; k++){
for(int l = j; l < j+m; l++){
tmp += arr[k][l];
}
}
if(tmp > max) max = tmp;
}
}
cout << "#" << t << " " << max << '\n';
}
return 0;
}