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

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

 

2차원 누적 합 배열을 초기화하고, 완탐으로 모든 부분 행렬을 탐색한다.

정답으로 부분 행렬 원소들의 합이 최대인 값을 출력한다.

 

기본 이론

(누적 합 및 완탐에 둘 다 쓰임)

초록 영역을 구하기 위해선 파란 영역 두개를 빼준 후, 공통 영역인 빨간 영역을 더한다.

s를 누적합으로 치환하면,

 

 

이다.

 

해당 방식으로 누적합 배열을 초기화하고, 4중 for문을 돌며 모든 부분행렬에 대해 완탐한다.

padding을 주면 경계 조건 체크를 안해도 되므로 더 효율적이다. (안했음)

 

 

오답 기록

1. 정답이 음수인 경우가 있으므로, ans = 0으로 초기화하면 안된다.

2. a1이 a2를 넘어가면 안된다. (구현 실수)

 

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


public class Main {

  public static void main(String args[]) throws IOException {
    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 ans = Integer.MIN_VALUE;
    int[][] s = new int[N][M];

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < M; j++) {

        boolean v = i > 0;
        boolean h = j > 0;

        s[i][j] += Integer.parseInt(st.nextToken());

        if (v) {
          s[i][j] += s[i - 1][j];
        }

        if (h) {
          s[i][j] += s[i][j - 1];
        }

        if (v && h) {
          s[i][j] -= s[i - 1][j - 1];
        }
      }
    }

    for (int a2 = 0; a2 < N; a2++) {
      for (int b2 = 0; b2 < M; b2++) {
        for (int a1 = 0; a1 <= a2; a1++) {
          for (int b1 = 0; b1 <= b2; b1++) {

            int total = s[a2][b2];

            boolean v = a1 > 0;
            boolean h = b1 > 0;

            if (v) {
              total -= s[a1 - 1][b2];
            }

            if (h) {
              total -= s[a2][b1 - 1];
            }

            if (v && h) {
              total += s[a1 - 1][b1 - 1];
            }

            ans = Math.max(ans, total);
          }
        }
      }
    }

    System.out.println(ans);
  }
}