[SWEA] 2001. 파리 퇴치

문제

위의 그림처럼 M X M 사이즈의 2차원 배열이 입력되었을 때, N X N 사이즈의 부분 배열 원소의 합 중 최대값 출력

 

풀이방법

M의 최대크기가 30 이므로 완전탐색

 

소스코드

package samsung;

import java.util.*;

public class s_2001 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		for(int t = 1; t <= test; t++) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int[][] a = new int[n][n];
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					a[i][j] = sc.nextInt();
				}
			}
			
			int max = 0;
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					int sum = 0;
					for(int k = 0; k < m; k++) {
						for(int s = 0; s < m; s++) {
							if(i+k >= n || j + s >= n)
								continue;
							sum += a[i + k][j + s];
						}
					}
					max = Math.max(max, sum);
				}
			}
			System.out.println("#" + t + " " + max);
		}
	}
}