C++ SWEA 2001. 파리 퇴치

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PzOCKAigDFAUq&categoryId=AV5PzOCKAigDFAUq&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1

SW Expert Academy

풀이

누적합문제로

https://jxxngho.tistory.com/109

C++ 백준 11660번 : 구간 합 구하기 5

저번에 포스팅한 누적합으로 배열을 채워준 후에

만약  M=2이라면  (2,2)부터 (N,N)까지 움직이면서 정답을 찾아주었다. 순회하면서

이 때 죽은 파리의 개수는 1+4+9+25 = 39

이 경우에는

68이 (1,1) ~ (3,3) 까지의 합이기 때문에 

파란색 부분을 빼주어야한다.

68 - 13{(1,1)~(3,1)까지의 합} - 7{(1,1)~(1,3)까지의 합)} 을 빼주고 두 번 뺀 (1,1)을 더해준다.

이를 일반식으로 나타내자면

ans = sum[i][j] - sum[i][j-M] - sum[i-M][j] + sum[i-M][j-M]

---

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

int main() {

	int cnt = 0;
	cin >> cnt;

	for (int k = 0; k < cnt; k++) {
		int N, M;
		cin >> N >> M;

		int tmp = 0;
		int sum[16][16] = { 0, };
		 
		for (int i = 1; i <= N; i++) {  // 누적합 구하기
			for (int j = 1; j <= N; j++) {
				cin >> tmp;
				sum[i][j] = tmp + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
			}
		}


		int ans = 0;
		for (int i = M; i <= N; i++) {
			for (int j = M; j <= N; j++) { // M*M 최대합 구하기 
				int tmp2 = sum[i][j] - sum[i][j-M] - sum[i-M][j] + sum[i-M][j-M];
				if (ans < tmp2) ans = tmp2;

			}

		}
		cout <<"#"<<k+1<<" "<< ans << endl;
	}
	return 0;
}