[BOJ_1749] 점수따먹기

설명

---

각 행렬별로 직사각형 형태의 PrefixSum을 구한 배열을 가지고 구할 크기의 직사각형을 이전 직사각형 형태로 만들어서 빼는 작업을 수행했습니다.

 

코드를 시각화 하자면

 

아래 그림과 같이 검은 직사각형 형태들로 내가 구하고 싶은 행렬인 빨간색 직사각형을 구하는 방식을 진행합니다.

 

사실 난이도에 비해서는 쉬운 문제였습니다. 별다른 기법이 필요한 것은 아니고 일반적인 구현 문제와 비슷합니다.

 

 

 

 

코드

---

package BOJ.prefix_sum;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class BOJ_1749 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer tk = new StringTokenizer(in.readLine());

        int N = Integer.parseInt(tk.nextToken());
        int M = Integer.parseInt(tk.nextToken());

        int[][] arr = new int[N + 1][M + 1];
        int[][] sum = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++){
            tk = new StringTokenizer(in.readLine());
            for (int j = 1; j <= M; j++){
                arr[i][j] = Integer.parseInt(tk.nextToken());
            }
        }


        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= M; j++){
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
            }
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                for (int k = i; k <= N; k++) {
                    for (int l = j; l <= M; l++) {
                        int val = sum[k][l] - sum[i - 1][l] - sum[k][j - 1] + sum[i - 1][j - 1];
                        ans = Math.max(ans,val);
                    }
                }
            }
        }
        bw.write(String.valueOf(ans));
        bw.flush();
        bw.close();
    }
}

 

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