[백준] 1749: 점수따먹기 - JAVA

27 Aug 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

n * m 행렬에서 직사각형의 구간을 잡아 구간의 합의 최대값을 구하는 문제이다.

입력을 받으면서 n * m 행렬을 누적합으로 저장했다.

board[i][j] = Integer.parseInt(st.nextToken()) + board[i - 1][j] + board[i][j - 1] - board[i - 1][j - 1];

탐색을 해서 최댓값을 구해야 하는데 구간의 길이가 정해져 있지 않으므로 행시작/끝, 열시작/끝 4중for문을 통해 탐색해야 한다.

열 시작을 rs, 끝을 re, 행 시작을 cs, 끝을 ce로 하여 정답을 갱신했다.

ans = Math.max(ans, board[re][ce] - board[rs - 1][ce] - board[re][cs - 1] + board[rs - 1][cs - 1]);

---

메모리: 20764KB

시간: 1344ms

언어: 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 + 1][m + 1];
        for (int i = 1; i < n + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < m + 1; j++) {
                board[i][j] = Integer.parseInt(st.nextToken()) + board[i - 1][j] + board[i][j - 1]
                        - board[i - 1][j - 1];
            }
        }

        int ans = Integer.MIN_VALUE;
        for (int rs = 1; rs < n + 1; rs++) {
            for (int cs = 1; cs < m + 1; cs++) {
                for (int re = rs; re < n + 1; re++) {
                    for (int ce = cs; ce < m + 1; ce++) {
                        ans = Math.max(ans,
                                board[re][ce] - board[rs - 1][ce] - board[re][cs - 1] + board[rs - 1][cs - 1]);
                    }
                }
            }
        }

        System.out.println(ans);
    }

}