[문제] SWEA 2001번 파리 퇴치

* 출처 swea D2

swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

내 생각

 

- 이차원 배열 완전 탐색!

처음에 matrix와 크기가 동일한 배열을 추가해서 파리채가 들어갈 수 있는 합을 하나씩 저장하려고 했다.

하지만 이럴 필요가 없다는 걸 알게됐다. 그냥 행,열 순회하면서 파리채가 담을 수 있는 영역(범위 확인)의 파리 합을 변수에다가 계속 저장만 하면 된다.

그래서 findSum() 함수를 만들었다.

public class Solution {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int T = Integer.parseInt(in.readLine());	// 테스트 케이스 수
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(in.readLine()," ");
			int N = Integer.parseInt(st.nextToken());	// N: 매트릭스 크기
			int M = Integer.parseInt(st.nextToken());	// M: 파리채 크기
			
			int[][] matrix = new int[N][N];
			
			//init matrix
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(in.readLine()," ");
				for(int j=0;j<N;j++) {
					matrix[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
            //최대값 구하기
			int sum = 0;
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					sum = Math.max(sum, findSum(matrix,i,j,N,M));
				}
			}
			System.out.println("#"+tc + " "+ sum);
		}

	}
	// 매트릭스의 (i,j) 위치에서 m 만큼 크기인 파리채가 포함된 영역의 합 구하기
	static int findSum(int[][] arr, int i, int j,int n, int m) {
		int sum = 0;
		for(int a=0;a<m;a++) {
			for(int b=0;b<m;b++) {
				int x = i+a;
				int y = j+b;
				if(x<n && y<n) {
					sum += arr[x][y];
				}
			}
		}
		return sum;
	}
}