[Java] SWEA - 파리 퇴치

n*n의 격자에서 m*m크기의 가장 큰 합을 구하는 문제입니다.

각 배열에 대한 누적합을 구해주었습니다.

map[i][j] = num + map[i-1][j] + map[i][j-1] - map[i-1][j-1];

구해진 누적합으로 계산해서 가장 큰 값이 나오는 값을 출력해주었습니다. 

 

import java.util.Scanner;
 
class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int ts = sc.nextInt();
        for(int t=0; t<ts; ++t) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int ans = 0;
            int[][] map = new int[n+1][n+1];
            for(int i=1; i<=n; ++i) {
                for(int j=1; j<=n; ++j) {
                    int num = sc.nextInt();
                    map[i][j] = num + map[i-1][j] + map[i][j-1] - map[i-1][j-1];
                }
            }
            for(int i=m; i<=n; ++i) {
                for(int j=m; j<=n; ++j) {
                    ans = Math.max(ans, map[i][j] - map[i-m][j] - map[i][j-m] + map[i-m][j-m]); 
                }
            }
            System.out.printf("#%d %d %n", t+1, ans);
        }
    }
}