[SWEA] 2001. 파리퇴치 (JAVA)

:D 문제

---

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부터 시작한다.)

 

SW Expert Acadmy

SW Expert Academy

 

 

:D 풀이 방법

---

n은 파리가 존재하는 판의 크기이고, m은 파리채의 크기이다. 그래서 판을 탐색하기 위해 n - m + 1 까지 범위를 설정했다. 

(만약 판의 크기가 4이고, 파리채의 크기가 2일 경우, 총 가로 방향으로 3번, 세로 방향으로 3번 탐색이 가능하다.)

 

그리고 안쪽 for문에서 파리채 크기만큼 주변을 탐색하여 파리의 합을 구하여 maxSum과 비교하여 문제를 풀었다.

 

 

:D 작성 코드

---

package sw.expert.academy.exam2001;

import java.util.Scanner;

public class Solution2001H {

    public static void main(String args[]) {
        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[][] board = new int[n][n];
            int sum = 0, maxSum = 0;

            // board 판
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    board[i][j] = sc.nextInt();
                }
            }

            // 합 계산 및 maxSum 설정
            for (int i = 0; i < n - m + 1; i++) {
                for (int j = 0; j < n - m + 1; j++) {
                    sum = 0;
                    for (int k = 0; k < m; k++) {
                        for (int l = 0; l < m; l++) {
                            sum += board[i + k][j + l];
                        }
                    }
                    if (maxSum < sum) {
                        maxSum = sum;
                    }
                }
            }
            System.out.println("#" + test_case + " " + maxSum);
        }
    }
}

 

 

 

 

마무리

알고리즘을 꾸준히 풀고 있지만, 아직까지도 어려운 부분이 많은 것 같다..! 더 많이 고민해보고 풀어봐야겠다!