[SW Expert Academy / JAVA] 2001.파리 퇴치

이번에 풀 문제는 2001번 파리 퇴치이다.

 

먼저 문제를 보자.

 

문제

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

아래는 N=5의 예이다.

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

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

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

이야, 벌써 머리가 아파온다.

일단 N X N 배열이라니 2차원 배열을 써야 하는 것 같다.

 

다음 조건을 봐 보자.

 

제약 사항

1. N 은 5 이상 15 이하이다.

2. M은 2 이상 N 이하이다.

3. 각 영역의 파리 개수는 30 이하이다.

 

 

그다음은 입출력이다.

 

입력

 

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
...

 

배열의 값부터 크기까지 일일이 다 받는 문제이다.

 

그러면 이제 코드를 봐 보자.

 

public class Solution_2001_SWExpertAcademy {
    static int max,n,m;   // n*n : 배열의 개수, m*m : 파리채 크기
    static int[][] area;  // 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int tc = 1; tc <= T; tc++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            area = new int[n][n];

            for(int i = 0; i < n; i++){ // 배열에 값 집어넣는 for문
                st = new StringTokenizer(br.readLine()," ");
                for(int j = 0; j < n; j++){
                    area[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            max = 0;
            // 모든 경우의 수 구하기
            for(int i = 0; i <= n - m; i++){
                for(int j = 0; j <= n-m; j++){
                    getMax(i,j);
                }
            }

            System.out.println("#" + tc + " " + max);
        }

    }

    // 파리체 크기의 배열의 합 구하기
    static void getMax(int x, int y){
        int sum = 0;
        for(int i = x; i < x + m; i++){
            for(int j = y; j < y + m; j++){
                sum += area[i][j];
            }
        }
        if(max < sum)
            max = sum;
    }

이게 StringTokenizer를 사용한 건데 그냥 BufferedReader 써도 상관없다. 물론 String 배열로 값을 받아야 하겠지만.

 

여기선 사실 getMax부분만 설명하면 될 것 같으니 빠르게 설명해 주겠다.

 

우리는 먼저 매게 변수로 for문에 i와 j를 넘겨주게 되는데 이 값의 최댓값이 n - m이다. 

이유는 파리채 크기만큼만 확인하면 되니 일일이 하나하나씩 다 돌아볼 필요가 없기 때문이다.

m = 2고 n이 3일 때

 

이런 식으로 배열이 생기게 될 것이다.

이때 M*M은 4이므로

맨 처음을 잡게 되면 빨간 줄 안에 있는 파리들을 잡을 것이다.

이런 식으로 검사를 하여

그다음 한 번 더 검사하면 배열의 끝에 다다른다.

이때 움직인 횟수는 2번이고 우린 for문에서 <=를 사용했기에 i , j <= n - m의 값은 2가 된다.

 

이러한 이유로 getMax에 있는 for문도 원리가 같다.

파리채의 시작 크기와 시작 크기부터 + 파리채 크기를 하여 for문을 돌린다.

그렇게 2차원 배열을 돌리며 sum의 변수를 더해준다.

그리고 전역 변수로 선언해준 max가 sum보다 적다면 sum으로 바꿔준다.

 

이렇게 모든 경우의 수를 다 구해 max값을 찾아 출력하면 끝.