[SWEA] 2001번 - 파리 퇴치 [Java]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq

 

[SWEA] 2001번 - 파리 퇴치 [Java]

[SWEA] 2001번 - 파리 퇴치 [Java]

[SWEA] 2001번 - 파리 퇴치 [Java]

---

1.  아이디어

 

N의 크기가 작아서 배열의 각 점에서 파리채를 전부 내리쳐보는 브루트포스 알고리즘으로 해결이 가능하고 누적합 배열을 활용해도 해결이 가능하다.

---

2. 문제풀이

 

브루트포스는 배열의 해당 점이 파리채의 왼쪽 위가 위치한다고 가정하고 4중 for문을 활용했다. 누적합 배열은 2차원 누적합으로 1행 1열부터 r행 c열까지 두 점을 대각점으로 하는 직사각형의 넓이가 저장되게 했다.

---

3. 코드

 

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

public class Solution {
    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(Solution.class.getResourceAsStream("input.txt")));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            int[][] map = new int[N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());

                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int max = 0;
            for (int i = 0; i <= N - M; i++) {
                for (int j = 0; j <= N - M; j++) {
                    int sum = 0;

                    for (int a = i; a < i + M; a++) {
                        for (int b = j; b < j + M; b++) {
                            sum += map[a][b];
                        }
                    }

                    max = Math.max(max, sum);
                }
            }

            sb.append("#").append(tc).append(" ").append(max).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

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

public class Solution {
    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(Solution_DP.class.getResourceAsStream("input.txt")));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            int[][] map = new int[N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());

                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int[][] prefixSum = new int[1 + N][1 + N];
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + map[i - 1][j - 1];
                }
            }

            int max = 0;
            for (int i = M; i <= N; i++) {
                for (int j = M; j <= N; j++) {
                    max = Math.max(max, prefixSum[i][j] - prefixSum[i - M][j] - prefixSum[i][j - M] + prefixSum[i - M][j - M]);
                }
            }

            sb.append("#").append(tc).append(" ").append(max).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기

 

- 브루트포스 알고리즘

- 누적합