[백준] 1749번. 점수따먹기(JAVA)

문제

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

---

풀이(21분)

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

public class Main {

    static int N, M;
    static int[][] arr;
    static int[][] prefixSum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N + 1][M + 1];
        prefixSum = 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++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                prefixSum[i][j] = arr[i][j] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
            }
        }

        int answer = -1_000_000_001;

        for (int x1 = 1; x1 <= N; x1++) {
            for (int y1 = 1; y1 <= M; y1++) {
                for (int x2 = x1; x2 <= N; x2++) {
                    for (int y2 = y1; y2 <= M; y2++) {
                        int currentSum = prefixSum[x2][y2] - prefixSum[x1 - 1][y2] - prefixSum[x2][y1 - 1] + prefixSum[x1 - 1][y1 - 1];
                        answer = Math.max(answer, currentSum);
                    }
                }
            }
        }

        System.out.println(answer);
    }
}

---

문제 풀이 전략

 

누적합 배열을 구해둔 뒤 4중 for문을 이용하여 모두 dp를 수행하는 전략이다.

 

시간복잡도가 걱정될 수 있지만 for문의 조건을 자세히 보면 N, M <= 200이라는 범위 내에서 문제없이 해결될 수 있다는 것을 알 수 있다.

2차원 누적합이라는 알고리즘 자체도 주요한 분석이 될 수 있지만, 시간 복잡도를 계산해서 밀고 나갈 수 있는 확신이 더욱 중요한 것 같다.