[SWEA] D2 - 2001번 | 파리퇴치

EllievV·2024년 11월 14일

🐊 CodingTest

목록 보기

11/18

🔍 문제 보러 가기

N X N의 주어진 배열에서 M X M 크기의 격자를 순회하면서, 가장 많은 파리를 포함하는 영역을 찾아 그 파리 수를 반환

문제 상세 설명

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

아래는 N=5 의 예이다.

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

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

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

[제약 사항]

N 은 5 이상 15 이하이다.
M은 2 이상 N 이하이다.
각 영역의 파리 갯수는 30 이하 이다.

[입력]

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

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

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

[출력]

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

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

입력	출력
10 5 2 1 3 3 6 7 8 13 9 12 8 4 16 11 12 6 2 4 1 23 2 9 13 4 7 3 6 3 29 21 26 9 5 8 21 19 8 0 21 19 9 24 2 11 4 24 19 29 1 0 21 19 10 29 6 18 4 3 29 11 15 3 3 29	#1 49 #2 159

내 코드

package D2;

//SWEA D2 2001번 "파리 퇴치" 문제 풀이 

import java.util.*;

public class N2001 {
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		int T = scanner.nextInt();
		
		StringBuilder result = new StringBuilder();
		
		for (int i = 1; i <= T; i++) {
			int N = scanner.nextInt();
			int M = scanner.nextInt();
			
			int[][] arr = new int[N][N];
			
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < N; k++) {
					arr[j][k] = scanner.nextInt();
				}
			}
			result.append(String.format("#%d %d\n", i, solution(arr, N, M)));
		}
		System.out.print(result);
		scanner.close();
	}
	
	public static int solution(int[][] arr, int N, int M) {
		
		int maxFlies = 0; // 최대 파리 수를 저장할 변수
		
		for (int i = 0; i <= N - M; i++) {
			for (int j = 0; j <= N - M; j++) {
				int sum = 0;
				
				for (int x = 0; x < M; x++) {
					for (int y = 0; y < M; y++) {
						sum += arr[i + x][j + y];
					}
				}
				maxFlies = Math.max(maxFlies, sum);
			}
		}
		
		return maxFlies;
	}
}