2023. 7. 18. 18:18ㆍNYPC/NYPC 2022 예선
[문제]
최근 이상 기후로 인해 붐힐 마을에 모기가 많이 늘어났다. 마리드는 붐힐 마을 주민들을 돕기 위해 물풍선으로 모기들을 퇴치하려고 한다. 마리드는 기존의 십자 모양의 물풍선만으로 모기를 효율적으로 퇴치할 수 없다는 것을 깨달았고, 엑스 자 모양으로 터지는 물풍선을 새로 개발했다.
붐힐 마을은 N x N 크기의 2차원 배열로 표현할 수 있고, 배열의 각 칸에 존재하는 모기의 수가 주어진다.
마리드는 한 칸을 선택하여 물풍선을 놓고 터트린다. 물풍선을 터트리면 범위 으로 물줄기가 뻗어나가 모기를 퇴치할 수 있다. 예를 들어, 십자 모양의 경우, 물풍선을 터트린 칸에서 위쪽, 오른쪽, 아래쪽, 왼쪽의 개 칸 이내의 모든 모기를 퇴치한다. 엑스 자 모양의 경우, 네 개의 대각선 방향으로 개 칸 이내의 모든 모기를 퇴치한다.
마리드가 물풍선을 놓는 칸은 마을 안에 있어야만 하지만, 물풍선이 터지는 물줄기가 마을 밖으로 나가는 경우는 허용된다.
십자 모양 혹은 엑스 자 모양의 물풍선을 한 개 터트릴 때, 퇴치할 수 있는 모기 수의 최댓값을 계산하는 프로그램을 작성하시오.
[입력 형식]
첫 줄에 붐힐 마을의 크기를 나타내는 정수 과 물풍선의 범위를 나타내는 정수 이 공백으로 구분되어 주어진다. ( )
이어지는 개 줄의 번째 줄에는 붐힐 마을을 나타내는 배열의 i번째 행의 개의 칸에 존재하는 모기의 수를 나타내는 정수 개가 공백으로 구분되어 순서대로 주어진다. 이때, 주어지는 정수는 이상 이하이다.
[출력 형식]
첫 줄에 십자 모양 혹은 엑스 자 모양의 물풍선을 한 개 터트릴 때, 퇴치할 수 있는 모기 수의 최댓값을 출력한다.
[해설]
N과 M의 범위가 작으므로 단순 브루트포스로 풀어도 충분합니다.
모든 인덱스에 대해서 크기가 M인 폭탄을 터뜨릴 때, 십자 모양과 엑스 모양 중 최댓값을 구해주면 됩니다.
[C/C++ 코드]
#include <bits/stdc++.h>
using namespace std;
#define MAX 51
int n,m,arr[MAX][MAX],mx=0,sum;
void boom(int x,int y){
sum=0;
for(int i=1;i<=m;i++){
if(x-i>=1){
sum+=arr[x-i][y];
}
if(y-i>=1){
sum+=arr[x][y-i];
}
if(x+i<=n){
sum+=arr[x+i][y];
}
if(y+i<=n){
sum+=arr[x][y+i];
}
}
sum+=arr[x][y];
if(sum>mx){
mx=sum;
}
sum=0;
for(int i=1;i<=m;i++){
if(x-i>=1&&y-i>=1){
sum+=arr[x-i][y-i];
}
if(x+i<=n&&y+i<=n){
sum+=arr[x+i][y+i];
}
if(x-i>=1&&y+i<=n){
sum+=arr[x-i][y+i];
}
if(x+i<=n&&y-i>=1){
sum+=arr[x+i][y-i];
}
}
sum+=arr[x][y];
if(sum>mx){
mx=sum;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>arr[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
boom(i,j);
}
}
cout<<mx;
}