[SWEA] 2001. 파리 퇴치

문제

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다.
M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다.
죽은 파리의 개수를 구하라!

[제약 사항]
1. N 은 5 이상 15 이하이다.
2. M은 2 이상 N 이하이다.
3. 각 영역의 파리 갯수는 30 이하 이다.

 

풀이

1. n과 m의 범위가 작기 때문에 모든 경우를 해줘도 될 것 같다.
2. i <= (n-m), j<=(n-m) 의 범위에서 모든 (i,j)에 대하여 (i,j)를 시작점으로 하는 M X M 크기의 사각형 내의 파리의 합을 구해준다.
3. 합을 매번 최대 값과 비교하여 최댓값을 구한다.

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

public class Solution {
	static int max, n, m;
	static int[][] area;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			area = new int[n][n];
			for(int i=0; i<n; i++) {
				st = new StringTokenizer(br.readLine()," ");
				for(int j=0; j<n; j++) {
					area[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			max = 0;
            //모든 경우의 수를 구한다.
			for(int i=0; i<=n-m; i++) {
				for(int j=0; j<=n-m; j++) {
					getMax(i,j);
				}
			}
			System.out.println("#"+tc+" "+max);
		}
	}
	
	static void getMax(int x, int y) {
		int sum = 0;
		for(int i=x; i<x+m; i++) {
			for(int j=y; j<y+m; j++) {
				sum += area[i][j];
			}
		}
		if(max < sum) max = sum;
	}

}