[SW Expert Academy] 12712. 파리퇴치3 (java)

문제

시간 : 10개 테스트케이스를 합쳐서 C의 경우 30초 / C++의 경우 30초 / Java의 경우 30초 / Python의 경우 30초

메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내
N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개체 수를 의미한다.

 

아래는 N=5 의 예이다.

파리 킬러 스프레이를 한 번만 뿌려 최대한 많은 파리를 잡으려고 한다. 스프레이의 노즐이 + 형태로 되어있어, 스프레이는 + 혹은 x 형태로 분사된다. 스프레이를 M의 세기로 분사하면 노즐의 중심이 향한 칸부터 각 방향으로 M칸의 파리를 잡을 수 있다.

다음은 M=3 세기로 스프레이르 분사한 경우 파리가 퇴치되는 칸의 예로, +또는 x 중 하나로 분사된다. 뿌려진 일부가 영역을 벗어나도 상관없다.

한 번에 잡을 수 있는 최대 파리수를 출력하라.

---

[제약 사항]

1. N 은 5 이상 15 이하이다.
2. M은 2 이상 N 이하이다.
3. 각 영역의 파리 갯수는 30 이하 이다.

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,
다음 N 줄에 걸쳐 N x N 배열이 주어진다.

---

예시 입력
2
5 2
1 3 3 6 7
8 13 9 12 8
4 16 11 12 6
2 4 1 23 2
9 13 4 7 3
6 3
29 21 26 9 5 8
21 19 8 0 21 19
9 24 2 11 4 24
19 29 1 0 21 19
10 29 6 18 4 3
29 11 15 3 3 29

---

예시 출력
#1 64
#2 157

---

내 풀이

import java.util.*;
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[][] mat = new int[N][N];
            for (int i=0; i<N; i++) {
                for (int j=0; j<N; j++) {
                    mat[i][j] = sc.nextInt();
                }
            }
             
            int max = 0;
            for (int i=0; i<N; i++) {
                for (int j=0; j<N; j++) {
                    int count1 = mat[i][j];
                    int count2 = mat[i][j];
                    for (int r=1; r<M; r++) {
                        if (i-r>=0) count1+=mat[i-r][j];
                        if (i+r<N) count1+=mat[i+r][j];
                        if (j-r>=0) count1+=mat[i][j-r];
                        if (j+r<N) count1+=mat[i][j+r];
                         
                        if (i-r>=0 && j-r>=0) count2+=mat[i-r][j-r];
                        if (i+r<N && j-r>=0) count2+=mat[i+r][j-r];
                        if (i-r>=0 && j+r<N) count2+=mat[i-r][j+r];
                        if (i+r<N && j+r<N) count2+=mat[i+r][j+r];
                    }
                    int count = Math.max(count1,count2);
                    if (count >= max) max = count;
                }
            }
            System.out.printf("#%d %d\n", test_case, max);
        }
    }
}

분명 문제에서는 *노즐의 중심이 향한 칸부터 각 방향으로 M칸의 파리를 잡을 수 있다*고 하길래 +M 칸까지 잡는 걸로 계산했는데 예시출력과 달랐는데 M-1 칸의 파리까지만 잡을 수 있었다.