[BOJ 20543] 폭탄 던지는 태영이

https://www.acmicpc.net/problem/20543

20543번: 폭탄 던지는 태영이

 

- 문제 요약

 

양의 정수 N과 M이 첫 번째 줄에 주어집니다.(1<=M<=N<=2,000 (M은 홀수))

두 번째 줄부터는 N*N 사이즈의 맵이 주어집니다. 맵에는 각 위치의 높이가 주어집니다.(-2,147,483,648<=Map[i][j]<=0)

맵에 폭탄을 던지면 중심점을 기준으로 M*M만큼 맵의 높이가 깎입니다.

 

두 번째 줄부터 주어지는 맵은 태영이가 폭탄을 던지고 난 후의 맵입니다.

폭탄을 던지기 전의 맵의 상태를 출력하세요.

 

 

- 알고리즘 정리

 

폭탄 던지는 범위를 누적합으로 구해서 그리디 하게 돌리면 확인할 수 있습니다.

메모장이나 종이에 배열을 그려가며 누적합 식을 만들면 더 쉽게 풀 수 있습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 2001
typedef long long ll;
ll result[MAX][MAX],arr[MAX][MAX];
int n,m;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>arr[i][j];
			arr[i][j]*=-1;
		}
	}
	int r=m/2,s=r,e=n-r;        
	for(int i=s;i<e;i++){
		for(int j=s;j<e;j++){
			result[i][j]=arr[i-r][j-r];
			if(i-r-1>=0){
				result[i][j]-=arr[i-r-1][j-r];
			}
			if(j-r-1>=0){
				result[i][j]-=arr[i-r][j-r-1];
			}
			if(i-r-1>=0&&j-r-1>=0){
				result[i][j]+=arr[i-r-1][j-r-1];
			}
			if(i-m>=0){
				result[i][j]+=result[i-m][j];
			}
			if(j-m>=0)
				result[i][j]+=result[i][j-m];
			if(i-m>=0&&j-m>=0)
				result[i][j]-=result[i-m][j-m];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cout<<result[i][j]<<" ";
		}
		cout<<'\n';
	}
}

코드 제출 결과