[백준]1749 점수따먹기

 

문제

1749번: 점수따먹기

 

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

동주가 개발한 게임은 이렇다. 일단 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

내 풀이

 

모든 부분 행렬의 합을 비교해가며 최대의 값을 찾아야 하기 때문에 누적합을 활용하여 부분 행렬의 합을 구하는 연산을 줄이는 방향으로 문제를 해결을 해야겠다고 생각함 

 

문제에서 준 예시를 바탕으로 풀이를 해보면 

 

입력 값&amp;amp;amp;amp;amp;amp;nbsp;

누적합 배열

나는 누적합 배열이 (1,1) 을 기준으로 ( i, j ) 까지 i * j 행렬의 합을 나타내게 만들었다

이 말을 그림으로 풀어서 설명하면 

 

요롷게 했다는 의미이다 (하늘색 박스의 합으로 했다는 것이다)

그리고 나서 이 누적합 배열을 활용해서 원하는 부분행렬의 합을 구하는 것을 생각해보면 

요런 연산을 통해 원하는 노란색 부분 행렬의 합을 누적합을 이용하여 구할 수 있다

이것을 이제 모든 케이스를 구하기 위해 저 부분행렬의 행의 시작 부분, 끝부분, 열의 시작, 끝 으로 2 * 2 = 4중 for문으로 돌리면서 최대값을 갱신하는 식으로 구현하였다

 

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

public class Main {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static String src = "3 5\n" +
            "2 3 -21 -22 -23\n" +
            "5 6 -22 -23 -25\n" +
            "-22 -23 4 10 2";

    static int N, M, data[][], accumulateSum[][];

    public static void main(String[] args) throws IOException {
        //input= new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));

        StringTokenizer str;
        str = new StringTokenizer(input.readLine());
        N = Integer.parseInt(str.nextToken());
        M = Integer.parseInt(str.nextToken());

        data = new int[N + 1][M + 1];
        accumulateSum = new int[N + 1][M + 1];

        for (int i = 1; i <= N ; i++) {
            str = new StringTokenizer(input.readLine());
            for (int j = 1; j <= M; j++) {
                data[i][j] = Integer.parseInt(str.nextToken());
                accumulateSum[i][j] = accumulateSum[i][j - 1] + accumulateSum[i - 1][j] - accumulateSum[i - 1][j - 1] + data[i][j];
            }
        }

        int answer = Integer.MIN_VALUE;
        for (int rowS = 1; rowS <= N; rowS++) {
            for (int rowE = rowS; rowE <= N; rowE++) {
                for (int colS = 1; colS <= M; colS++) {
                    for (int colE = colS; colE <= M; colE++) {
                        answer = Math.max(answer, accumulateSum[rowE][colE] - accumulateSum[rowS - 1][colE] - accumulateSum[rowE][colS - 1] + accumulateSum[rowS - 1][colS - 1]);
                    }
                }
            }
        }
        System.out.println(answer);
    }

}

맞긴 했는데 메모리도 비슷하게 쓰면서 실행시간을 거의 1/3 로 줄이는 저 코드가 궁금하다...