[백준] 25708: 만남의 광장 - JAVA

https://www.acmicpc.net/problem/25708

 

풀이

길을 가로 2개, 세로 2개 만들어야 한다.

가로와 세로 각각 누적합을 만들어놓았다.

4중for문을 통해 up, down, left, right 를 탐색하여 구해놓은 누적합을 더해주고

겹치는 부분을 원 배열에서 찾아 빼주었다.

길로 둘러쌓인 부분의 개수를 더해야 하므로 `(down-up-1)\*(right-left-1)` 만큼 더해주었다.

 

---

 

메모리: 16892KB
시간: 312ms
언어: Java 11

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] board = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[] rowSum = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                rowSum[i] += board[i][j];
            }
        }

        int[] colSum = new int[m];
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                colSum[j] += board[i][j];
            }
        }

        int ans = Integer.MIN_VALUE;
        for (int up = 0; up < n; up++) {
            for (int down = up + 1; down < n; down++) {
                for (int left = 0; left < m; left++) {
                    for (int right = left + 1; right < m; right++) {
                        int sum = rowSum[up] + rowSum[down] + colSum[left] + colSum[right];
                        sum -= (board[up][left] + board[up][right] + board[down][left] + board[down][right]);
                        sum += (down - up - 1) * (right - left - 1);

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

        System.out.println(ans);
    }

}