[SW Expert D2] 2001. 파리 퇴치

2001. 파리 퇴치

SW Expert Academy

 

문제 분석

 

• N x N 배열 속 각 영역에 존재하는 파리의 개수를 알려준다
• M x M 파리채로 죽일 수 있는 가장 많은 파리 개수를 출력해라
• N, M은 입력으로 주어진다. 

 

해결 포인트

 

• 일단 시간 걱정은 없어도 된다 (  5 <= N <= 15, 2 <= M <= N | 시간 30초 )
• 구간 합
• 배열을 입력 받으면서 해당 인덱스까지 구간 합을 구한다. 

sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + nums[i][j];

 

• 구간 합을 가지고, [M][M] 번부터 가장 큰 M x M 구간 합을 찾는다.
• nums[i-M][j-M] 부터 nums[i][j] 까지의 구간 합

int newMax = sums[i][j] - sums[i-M][j] - sums[i][j-M] + sums[i-M][j-M];

 

• 배열은 N까지만 만들면 또 [0][0] 구간합 계산할 때 체크해야하는 부분이 늘기 때문에 N+1 까지 배열 만드는게 좋다.

 

코드

 

import java.util.Scanner;
import java.io.FileInputStream;

class Solution {
    public static void main(String args[]) throws Exception {
    
        Scanner sc = new Scanner(System.in);
        int T;
        T = sc.nextInt();

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = sc.nextInt();
            int M = sc.nextInt();

            int[][] nums = new int[N + 1][N + 1];
            int[][] sums = new int[N + 1][N + 1];

            for (int i = 1; i < N + 1; i++) {
                for (int j = 1; j < N + 1; j++) {
                    nums[i][j] = sc.nextInt();
                    sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + nums[i][j];
                }
            }

            int max = 0;
            for (int i = M; i < N + 1; i++) {
                for (int j = M; j < N + 1; j++) {
                    int newMax = sums[i][j] - sums[i-M][j] - sums[i][j-M] + sums[i-M][j-M];
                    max = Math.max(max, newMax);
                }
            }

            System.out.printf("#%d %d\n", test_case, max);
        }
    }
}