백준, BOJ, 20002번, 캠프 준비 C++ [CPP] ★★★★★

전형적인 브루트포스 문제지만

당연히 시간을 줄이는 방법이 있었다.누적합을 이용하는 것이다.★★★★★★

누적합에 대해선 따로 다시 공부해야겠다.

 

하지만 바로 생각하지 못해서 오래걸렸다.

 

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

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

int board[301][301];
long long sum[301][301];

long long ans = INT_MIN;

int main(){
    int N;
    cin >> N;
    
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=N; j++){
            cin >> board[i][j];
        }
    }
    
    //누적 합을 이용한다 => 바로 생각하지 못함...ㅠ
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=N; j++){
            sum[i][j] = board[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
        }
    }
    
    //최대인 값인 곳을 구함.
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=N; j++){
            int limit = min(N-i, N-j); //limit만큼의 정사각형 크기만 계산 가능
            //해당 지점에서 계산할 수 있는 모든 k 값 계산
            for(int k = 0; k<= limit; k++){
                ans = max(ans, sum[i+k][j+k] - sum[i-1][j+k] - sum[i+k][j-1] + sum[i-1][j-1]);
            }
        }
    }
    
    cout << ans << '\n';

    
    
    
    
    return 0;
}