[SWEA] 2001. 파리 퇴치

 

[SWEA] 2001. 파리 퇴치

 

SW Expert Academy

 

 

 

 

 

[입력]

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

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

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


[출력]

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

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

 

 

[풀이]

 

우선 4*4 형태의 배열일 경우, 2*2 정사각형 파리채로 잡으면 이 정사각형의 시작점인 맨위 맨왼쪽 칸이 인덱스 2까지 가능하다.

인덱스 3으로 시작하는 2*2 정사각형은 배열을 넘어가버린다.

이를 통제하기 위해 규칙을 찾아냈다.

N이 4일 경우 그리고 M이 2일 경우 인덱스 2까지 가능하므로 반복문의 범위를 N-M까지로 한다.

그리고 이렇게 가능한 시작점을 돌면서 또다시 이중 반복문을 만들어 M*M 정사각형 범위에 있는 숫자를 모두 더한다.

이 중 가장 큰 숫자를 저장하고 출력한다.

 

 

 

public class al2001 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		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 sum = 0;
			
			int[][] arr = new int[N][N];
			int r = Integer.MIN_VALUE; //최대 sum값이 담길 변수
		
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j] = sc.nextInt();
				}
			}
			
			for (int k = 0; k <= N-M; k++) { //파리채가 N이상으로 넘어가면 안되니까 N-M
				for (int l = 0; l <= N-M; l++) {
					sum = 0;
					for (int i = 0; i < M; i++) { //M길이의 정사각형의 합 구하기
						for (int j = 0; j < M; j++) {
							sum += arr[k+i][l+j];
						}
					}
					r = Math.max(r, sum); //최대값 찾아서 저장
				}
			}
			
			System.out.println("#" + test_case + " " + r);

		}
	}

}

• 24,212 kb메모리
• 162 ms실행시간
• 2,423코드길이
• Pass결과