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

(2021년 1월 16일에 작성한 글입니다.)

20543번: 폭탄 던지는 태영이

와...
진짜 신기한 문제다...

처음 풀이는
가장자리부터 값이 남아있는지 확인하고(시계 반대방향으로 돎)
만약 남아있다면 M * M 영역을 돌면서 값을 빼주는 걸 반복했다.
시간 안에 해결할 수 있을 줄 알았는데
역시 어림도 없었다.

그렇게 한참 고민하다 결국 풀이를 봤다
https://altheajang.blogspot.com/2021/01/ps-boj-20543.html
놓친 포인트는

1. 굳이 가장자리부터 확인하면서 시계방향으로 돌 필요가 없다.
그냥 for(i=1; i<=N; i++) for(j=1; j<=N; j++) 방식으로 for문 돌면서 확인해도 된다.
어차피 폭탄이 있을 수 없는 위치들이 있기 때문이다! (M != 1일때)
위에서부터 값을 지워주는 과정에서
만약 덜 지워지고 남은 값이 있다면 그 위치에는 폭탄이 있을 수 없다.
그 위치를 시작으로 오른쪽/아래로 M*M의 정사각형이 생겨야 하는거지.

2. 값을 지워줄 때 prefix sum을 이용할 수 있다.
arr[i][j]를 확인하는 상태라면, arr[i-M+1][j-M+1]부터 arr[i][j]까지
지금까지 얼마나 지워졌는지를 확인하고,
만약 지워져야 하는 값이 남아있다면, arr[i][j]를 시작으로 하는 M*M 정사각형이 있는거다.
즉 ans[i+M/2][j+M/2] += diff (diff는 남아있던 값)

우와...
진짜 신기가 방기다.

vector<vector<ll>> arr, sum;
int N, M;
ll getSum(int y, int x) {
	int yy = max(0, y - M), xx = max(0, x - M);
	return sum[y][x] - sum[yy][x] - sum[y][xx] + sum[yy][xx];
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	arr.resize(N + 5, vector<ll>(N + 5));

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> arr[i][j];
			arr[i][j] *= -1;
		}
	}
	
	//M == 1일때
	if (M == 1) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				cout << arr[i][j] << ' ';
			}
			cout << ENDL;
		}
		return 0;
	}
	
	//M != 1일때
	sum.resize(N + 5, vector<ll>(N + 5));
	vector<vector<ll>> ans(N + 5, vector<ll>(N + 5));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];

			ll diff = arr[i][j] - getSum(i, j);
			if (diff > 0) {
				sum[i][j] += diff;
				ans[i + M / 2][j + M / 2] += diff;
			}
		}
	}
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cout << ans[i][j] << ' ';
		}
		cout << ENDL;
	}
	
	return 0;
}

학회원 분의 풀이를 봤는데 엄청 신기했다.
네 가장자리에 M/2만큼 칸을 비워놓고, 중간에는 arr[1][1]부터 값이 들어가는 배열을 만든다.
그런 다음에 값을 채워놓은 부분부터 돌면서
ans[i][j] += arr[i][j] - arr[i-1][j] - arr[i][j-1] + arr[i-1][j-1];
ans[i][j] -= arr[i-M][j] + arr[i][j-M] - arr[i-M][j-M];
(인덱스 더 꼼꼼히 체크해야 함. 범위 확인해서)
이런 방식이었다.

arr[i][j] - arr[i-1][j] - arr[i][j-1] + arr[i-1][j-1]
이 부분은 arr[0][0]부터 arr[i][j]까지의 합이고
arr[i-M][j] + arr[i][j-M] - arr[i-M][j-M]를 빼줌으로서
arr[i-M+1][j-M+1]부터 arr[i][j]까지의 M*M 중에서 arr[i][j] 부분만 빠진
M*M-1 수들의 합이 구해진다.
이를 이용해서 얼마의 값이 더 필요한지 알 수 있다.

처음에는 prefix sum 형태가 아니라고 생각했는데 뜯어보니 맞구나.
그리고 이 코드에서
배열을 옮기셔서 ans[i][j]에 값이 바로 저장되게 했다는 것도 좋은 아이디어 인거 같다.



정말
신기가 방기다...