[C++] 백준 20543 폭탄 던지는 태영이

문제 링크

---

www.acmicpc.net/problem/20543

20543번: 폭탄 던지는 태영이

 

접근 방법

---

 처음 이 문제를 접근하였을 때 시간초과를 해결하는 것이 어렵지 않았습니다. 하지만 풀이법을 떠올렸을 때 신선한 충격을 받게 되었습니다. 부분합을 적절히 활용하면 n^2의 복잡도로 해결할 수 있었습니다. 

 

만약 폭탄의 범위가 3인 경우 한 지역은 범위내에 있는 폭탄의 영향을 받습니다. 

 

x지점은 색이 칠해져 있는 부분들의 폭탄의 합과 같다는 것을 유추 할 수 있습니다.

그러면 한 지점의 폭탄의 수는 위의 정보를 활용하여 구할 수 있습니다.

 

문제에서 주어진 누적합의 배열을 sum[N], 각각 폭탄을 나타내는 배열을 bomb[N]이라 하였을 때

아래 그림의 정보를 활용하면 bomb[16]의 값은 다음과 같이 구할 수 있습니다.   

bomb[16] = 도형A(sum[11]) - 도형B(sum[7]) - 도형C(sum[10]) + 도형D(sum[6]) + bomb[4] + bomb[13] - bomb[1]

 

이 식을 문제에 맞게 일반화 시키면

(r = M/2일 때)

bomb[i][j] = sum[i-r][j-r] - sum[i-r-1][j-r] - sum[i-r][j-r-1] + sum[i-r-1][j-r-1] + bomb[i-M][j] + bomb[i][j-M] - bomb[i-M][j-M]

이와 같이 정의 할 수 있습니다.

 

소스 코드

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long univ[2001][2001];
long long ans[2001][2001];
int N, M;

void printMap() {

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cout << ans[i][j] << " ";
		cout << "\n";
	}
}

void solve() {
	
	int r = M / 2;
	int start = r;
	int end = N - r;
	             
	for (int i = start; i < end; i++) {
		for (int j = start; j < end; j++) {
			ans[i][j] = univ[i - r][j - r];
			if (i - r - 1 >= 0) 
				ans[i][j] -= univ[i - r - 1][j - r];
			if (j - r - 1 >= 0) 
				ans[i][j] -= univ[i - r][j - r - 1];
			if (i - r - 1 >= 0 && j - r - 1 >= 0) 
				ans[i][j] += univ[i - r - 1][j - r - 1];
			if (i - M >= 0)
				ans[i][j] += ans[i - M][j];
			if (j - M >= 0)
				ans[i][j] += ans[i][j - M];
			if (i - M >= 0 && j - M >= 0)
				ans[i][j] -= ans[i - M][j - M];
		}
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			long long num; cin >> num;
			univ[i][j] = -1 * num;
		}
	}

	solve();
	printMap();
}