[C++] 백준 2829 아름다운 행렬 [Gold3]

풀이

정사각 행렬의 주대각선 합과 나머지 대각선 합의 차이의 최대값을 구하는 문제.

N<=400 이므로, {정사각형 크기 결정 - row결정 - col결정 - Diagonal 계산} 반복문의 경우 O(N^4) =  25,600,000,000이다.

구간합 아이디어를 적용해 Diagonal 계산 for loop를 없앤다면 O(N^3) = 64,000,000 으로 1초 제한에 걸리지 않는다.

 

1. 입력을 받아올 때 주대각선 구간합 벡터 main_d 와 나머지 대각선 구간합 벡터 sub_d를 업데이트 한다.

2. 이때 sub_d는 오른쪽 끝 열을 0으로 만들도록 채운다.

3. 3중 for loop로 현재 (정사각형 크기, row, col)에서 주대각선 합과 나머지 대각선 합을 구한 후 차이를 업데이트 한다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    // freopen("2829.txt", "r", stdin);
    
    int N, num;
    cin >> N;
    vector<vector<int>> sub_d(N+1, vector<int> (N+1, 0));
    vector<vector<int>> main_d(N+1, vector<int> (N+1, 0));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> num;
            // Diagonal Prefix Sum
            main_d[i+1][j+1] = main_d[i][j] + num;
            sub_d[i+1][j] = sub_d[i][j+1] + num;
        }  
    }

    int ans = 0;
    for (int area = 2; area <= N; area++) {
        // 크기 2인 정사각 행렬부터 N까지 검사
        for (int row = 0; row < N+1-area; row++) {
            for (int col = 0; col < N+1-area; col++) {
                // 대각선 구간합 가져오기
                int md = main_d[row+area][col+area] - main_d[row][col];
                int sd = sub_d[row+area][col] - sub_d[row][col+area];
                ans = max(md - sd, ans);
            }   
        }
    }
    cout << ans << "\n"; 
    return 0;
}