문제
상근이는 이상하게 정사각행렬을 아름답다고 생각한다. 상근이는 행렬이 얼마나 아름다운지를 수치로 나타낸다.
A를 행렬의 주 대각선 성분의 합이라고 하자. 또, B는 또다른 대각선 성분의 합이라고 하자. 이때, 행렬의 아름다운 정도는 A-B가 된다.
NxN크기의 행렬이 주어졌을 때, 아름다운 정도가 가장 큰 부분 행렬을 구하는 프로그램을 작성하시오.
주 대각선은 행렬의 가장 왼쪽 위에서 시작하는 대각선이다.
입력
첫째 줄에 행렬의 크기 N이 주어진다. (2 <= N <= 400) 다음 N개의 줄에는 행렬의 성분이 공백으로 구분되어 주어진다. 각 성분은 [-1000,1000] 범위 안에 들어있다.
출력
첫째 줄에 입력으로 주어진 행렬의 부분 행렬 중 아름다운 정도가 가장 큰 것의 아름다운 정도를 출력한다.
풀이
처음에는 모든 부분 정사각행렬을 잡고 그 안의 두 대각선을 직접 더하면 될 것 같지만, 그렇게 하면 구간합 계산이 너무 비싸다. 이 문제는 대각선 방향으로 누적합을 미리 만들어 두면 훨씬 단순해진다.
배열 구간합을 구할 때 핵심은 두 방향의 대각선을 각각 다른 형태의 누적합 배열로 만드는 것이다. 정방향 대각선 합은 왼쪽이 한 칸 비어 있는 배열처럼 두고 matrix[i + 1][j + 1] = value + matrix[i][j] 형태로 쌓는다. 그러면 같은 주 대각선 위의 값들이 계속 이어져서 저장된다.
반대로 역방향 대각선 합은 오른쪽이 한 칸 비어 있는 배열처럼 두고 reverseMatrix[i + 1][j] = value + reverseMatrix[i][j + 1]로 누적한다. 이렇게 하면 반대 대각선 방향의 합도 같은 방식으로 빠르게 뽑아낼 수 있다.
이제 왼쪽 위 좌표가 (i, j)이고 한 변의 길이가 k인 부분 정사각행렬을 보자. 주 대각선 합은 matrix[i + k][j + k] - matrix[i][j]로 구할 수 있고, 반대 대각선 합은 reverseMatrix[i + k][j] - reverseMatrix[i][j + k]로 구할 수 있다. 결국 모든 부분 정사각행렬을 순회하되, 각 행렬의 아름다운 정도 계산은 에 끝난다.
즉 전체 흐름은 "모든 부분 정사각행렬을 브루트포스로 보되, 대각선 합 계산만 누적합으로 줄인다"이다. 대각선 누적합 배열을 어떻게 잡느냐가 사실상 문제의 전부였다.
코드
import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int[][] matrix, reverseMatrix;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
matrix = new int[N + 1][N + 1];
reverseMatrix = new int[N + 1][N + 1];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int value = Integer.parseInt(st.nextToken());
matrix[i + 1][j + 1] = value + matrix[i][j];
reverseMatrix[i + 1][j] = value + reverseMatrix[i][j + 1];
}
}
System.out.println(solve());
}
private static int solve() {
int beauty = 0;
for (int k = 2; k <= N; k++) {
for (int i = 0; i <= N - k; i++) {
for (int j = 0; j <= N - k; j++) {
int A = matrix[i + k][j + k] - matrix[i][j];
int B = reverseMatrix[i + k][j] - reverseMatrix[i][j + k];
beauty = Math.max(beauty, A - B);
}
}
}
return beauty;
}
}복잡도
- 시간 복잡도: 모든 부분 정사각행렬의 위치와 크기를 확인하므로 이다.
- 공간 복잡도: 두 방향의 대각선 누적합 배열을 저장하므로 이다.
마무리
부분 행렬을 전부 보긴 해야 하지만, 대각선 합까지 매번 다시 구할 필요는 없다. 정방향과 역방향 대각선을 서로 다른 모양의 누적합 배열로 만들어 두면, 결국 이 문제는 브루트포스와 구간 계산의 조합으로 정리된다.
