[JAVA][D2] 2001. 파리 퇴치

문제 

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다.

아래는 N=5 의 예이다.
 



M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다.

죽은 파리의 개수를 구하라!

예를 들어 M=2 일 경우 위 예제의 정답은 49마리가 된다.
 



[제약 사항]

1. N 은 5 이상 15 이하이다.

2. M은 2 이상 N 이하이다.

3. 각 영역의 파리 갯수는 30 이하 이다.


[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,

다음 N 줄에 걸쳐 N x N 배열이 주어진다.


[출력]

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

예시

 

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			// 입력된 반복수
			int caseCount = Integer.parseInt(br.readLine());
			for (int i = 1; i <= caseCount; i++) {
				String[] str = br.readLine().split(" ");
				int N = Integer.parseInt(str[0]);
				int M = Integer.parseInt(str[1]);
				int max = 0;
				int[][] nums = new int[N][N];
				// 입력된 파리개수 넣기
				for (int x = 0; x<N; x++) {
					String[] lineNums = br.readLine().split(" ");
					for (int y = 0; y<N; y++) {
						// 문자->숫자
						nums[x][y] = Integer.parseInt(lineNums[y]);
					}
				}
				//0부터 N-M만큼 반복(내부에서 M만큼 반복하기 때문에 제한을 걸어둬서 예외발생하지 않도록 설정)
				for (int x=0; x<=N-M; x++) {
					for (int y=0; y<=N-M; y++) {
						int sum=0;
						//x축을 기준으로 M만큼까지의 숫자들을 모두 더함
						for(int a=x;a<x+M;a++) {
							for(int b=y;b<y+M;b++) {
								sum+=nums[a][b];
							}
						}
						if(max<sum) {
							max=sum;
						}
					}
				}
				System.out.println("#"+i+" "+max);
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

}