[ BOJ ][JAVA][1749] 점수따먹기

www.acmicpc.net/problem/1749

1749번: 점수따먹기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	367	115	88	31.655%

문제

동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점수 따먹기라는 게임인데 그다지 재밌어 보이지는 않는다.

동주가 개발한 게임은 이렇다. 일단 N*M 행렬을 그린 다음, 각 칸에 -10,000 이상 10,000 이하의 정수를 하나씩 쓴다. 그런 다음 그 행렬의 부분행렬을 그려 그 안에 적힌 정수의 합을 구하는 게임이다.

동주가 혼자 재밌게 놀던 중 지나가는 당신을 보고 당신을 붙잡고 게임을 하자고 한다. 귀찮은 당신은 정수의 합이 최대가 되는 부분행렬을 구하여 빨리 동주에게서 벗어나고 싶다.

입력

첫째 줄에 N (1 < N < 200), M (1 < M < 200)이 주어진다. 그 다음 N개의 줄에 M개씩 행렬의 원소가 주어진다.

출력

첫째 줄에 최대의 합을 출력하라.

예제 입력 1

3 5
2 3 -21 -22 -23
5 6 -22 -23 -25
-22 -23 4 10 2

예제 출력 1

16

코드

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

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

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + board[i][j];
            }
        }

        // 모든 경우를 다 체크하면서 돌아도 범위가 여유롭기 때문에 시간초과가 안난다 ! -> 브루트포스
        long max = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int x = i; x <= n; x++) {
                    for (int y = j; y <= m; y++) {
                        long result = prefixSum(i, j, x, y, dp);
                        max = Math.max(max, result);
                    }
                }
            }
        }

        System.out.println(max);
    }
    static long prefixSum(int x1, int y1, int x2, int y2, int[][] psum) {
        return psum[x2][y2] - psum[x1 - 1][y2] - psum[x2][y1 - 1] + psum[x1 - 1][y1 - 1];
    }
}