[SWEA] 2001. 파리 퇴치

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq

풀이

🔥 예전에 4중 for문을 이용해서 풀었던 문제인데 이번에 누적합을 통해 O(N^2) 다시 풀었다. 누적합 이차원배열을 완성하고 그 배열을 이용해서 MxM 범위 안에서 누적합을 구한다. -M만큼 왼쪽, 위에 해당하는 위치의 값을 이용해서 i j의 누적합 값에서 MxM 범위의 합만 남도록 한다.
크게 두 배열이 필요한건데 누적합 배열과 MxM범위에 대한 합에 대한 배열이다. 근데 후자에 해당하는 배열은 굳이 만들 필요없었고 바로 max와 비교를 통해서 바로 최대값을 구했다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Solution_2001_이광용 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int tc = Integer.parseInt(br.readLine());
		
		for(int t = 1 ; t<= tc; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			
			int[][] map = new int[n+1][n+1];
			int[][] sigma = new int[n + 1][n + 1];//누적합 이차원 배열
			
			for(int i = 1 ; i <= n; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 1; j <= n; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					//해당 i j 위치의 누적합 = 누적합 배열의 왼쪽 칸 + 누적합 배열의 왼쪽 칸 - 누적합 배열의 대각선 칸(겹쳐서 두번 더해지므로 한번 빼준다.) + 해당 위치의 원소값
					sigma[i][j] = sigma[i][j-1] + sigma[i-1][j] - sigma[i-1][j-1] + map[i][j];
				}
			}
			
			//누적합 이차원 배열을 이용해서 MxM 범위에 해당하는 값들의 최대값을 구해서 갱신해나간다.
			//MxM의 범위의 누적합을 구하는 방법
			//누적합 배열을 이용한 i j 해당 위치에서 MxM 범위의 누적합
			// = 누적합 배열의 (i, j)의 값 - 왼쪽에 해당하는 (i, j-m)의 값 - 위쪽에 해당하는 (i - m, j)의 값  + 대각선에 해당하는 (i-m, j-m)의 값 (두 번 빼지기때문에 한번 더해줌)
			int max =Integer.MIN_VALUE;
			for(int i = m; i <= n; i++) {
				for(int j = m; j <= n; j++) { //m,m부터 시작
					max = Math.max(max,
							sigma[i][j] - sigma[i][j-m] - sigma[i-m][j] + sigma[i-m][j-m]);
				}
			}
			bw.write("#"  + t + " " + max);
			bw.newLine();
		}
		bw.flush();
		br.close();
		bw.close();
		
		
	}
}