[SWEA] 2001번 : 파리 퇴치

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq&categoryId=AV5PzOCKAigDFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=JAVA&select-1=2&pageSize=10&pageIndex=1

SW Expert Academy

 

문제

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

 

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

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

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

 

제약 사항

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

 

입력

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

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

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

 

출력

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

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

 

---

소스코드

import java.io.*;
import java.util.StringTokenizer;

class Solution {
    static int m;
    static int arr[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            arr = new int[n][n];

            // 입력값 배열 저장
            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < n; k++) {
                    arr[j][k] = Integer.parseInt(st.nextToken());
                }
            }

            int max = Integer.MIN_VALUE;
            // 파리채 칠 수 있는 영역 탐색
            for (int j = 0; j < n - m + 1; j++) {
                for (int k = 0; k < n - m + 1; k++) {
                    // 해당 영역 파리 합계 구하기
                    int sum = sum(j, k);
                    if(max < sum) max = sum;
                }
            }

            sb.append("#" + (i + 1) + " " + max + "\n");
        }

        System.out.println(sb);
    }

    // MxM 영역 파리 개수 구하는 로직
    static int sum(int x, int y) {
        int sum = 0;
        for (int i = x; i < x + m; i++) {
            for (int j = y; j < y + m; j++) {
                sum += arr[i][j];
            }
        }
        return sum;
    }
}

 

해결 방법

1. 파리채를 칠 수 있는 영역에 대한 탐색을 진행한다.
2. 그 영역에 대한 파리의 수 합계를 구한다.
3. 합계와 최댓값을 비교하여 합계가 더 크다면 최댓값을 갱신한다.