[백준] 1749번 - 점수따먹기 (Gold 4)

문제 링크

백준 1749번 - 점수따먹기 (Gold 4)

문제 설명

N x M 행렬(1 < N, M < 200)의 각 칸에 -10000 이상 10000 이하의 정수가 하나씩 쓰여져 있다.
이 행렬의 부분행렬의 정수의 합의 최댓값을 구하시오.

정답 코드 및 설명

전체 경우의 수를 다음과 같은 방법으로 탐색한다.

1. 부분행렬의 시작 행과 끝 행을 고정한다.
2. 시작 행과 끝 행 사이의 행을 모두 합친 하나의 새로운 행 columnSubSum을 만든다.
   • 이 과정은 누적합을 활용해서 수행하면 더 빠르다.
3. columnSubSum의 부분합 중 최댓값을 구한다.
   • 이 과정은 DP를 활용한다.
   • 끝 원소가 i번째 원소인 부분합 중 최댓값을 maxSubSum[i]로 두자.
   • 끝 원소가 i+1번째 원소인 부분합에는 두 가지 경우가 있다.
     • i+1번째 원소 하나로만 이루어진 부분합
     • 끝 원소가 i번째 원소인 부분합에 i+1번째 원소를 합한 경우
   • 점화식으로 표현하면 $\textrm{maxSubSum}[i+1] = \textrm{max}(\textrm{maxSubSum}[i], 0) + \textrm{columnSubSum}[i+1]$
4. 시작 행과 끝 행을 변화시키면서 1~3을 반복하여 최댓값을 얻는다.

전체 시간 복잡도를 계산해보자.

• columnSubSum을 만들기 위한 누적합 계산 : $O(NM)$
• 시작 행과 끝 행을 변화시키는 경우의 수 : $N(N-1)/2$
  • 각 경우마다 columnSubSum을 만들기 : $O(M)$
  • columnSubSum의 부분합 중 최댓값 구하기 : $O(M)$
• 전체 시간 복잡도 : $O(NM) + O(N^2M) = O(N^2M)$

columnSubSum을 만들 때 누적합을 활용하지 않았다면, 각 경우마다 $O(NM)$의 시간 복잡도가 들어간다.
이 경우 전체 시간 복잡도는 $O(N^3M)$으로, 시간 초과가 발생할 우려가 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1749 {
    static final int MIN = -400000000;
    int n, m;
    int[][] arr;

    void input() 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());
        arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    int maxSum() {
        int maxSum = MIN;
        int[][] columnCumulativeSum = new int[n + 1][m];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                columnCumulativeSum[i][j] = columnCumulativeSum[i - 1][j] + arr[i - 1][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int[] columnSubSum = new int[m];
                for (int k = 0; k < m; k++)
                    columnSubSum[k] = columnCumulativeSum[j][k] - columnCumulativeSum[i][k];
                int maxSubSum = maxSubSum(columnSubSum);
                if (maxSum < maxSubSum)
                    maxSum = maxSubSum;
            }
        }
        return maxSum;
    }

    int maxSubSum(int[] arr) {
        int[] maxSubSum = new int[arr.length];
        maxSubSum[0] = arr[0];
        int max = maxSubSum[0];
        for (int i = 1; i < arr.length; i++) {
            maxSubSum[i] = arr[i];
            if (maxSubSum[i - 1] > 0) maxSubSum[i] += maxSubSum[i - 1];
            if (max < maxSubSum[i])
                max = maxSubSum[i];
        }
        return max;
    }

    void solution() throws IOException {
        input();
        System.out.println(maxSum());
    }

    public static void main(String[] args) throws IOException {
        new BOJ1749().solution();
    }
}