[BOJ/백준][Gold4] 1749 : 점수따먹기 (C++)

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

1749번: 점수따먹기

 

[난이도] Gold4
[유형] 누적합

[풀이]
누적합을 미리 구해준 뒤 나올 수 있는 모든 부분행렬을 구해보면 됩니다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,board[201][201],ans=-9e8;
int sol(int h,int w){
    int ret=-9e8;
    for(int i=1;i<=N-h+1;i++)
        for(int j=1;j<=M-w+1;j++)
            ret=max(ret,board[i+h-1][j+w-1] - board[i-1][j+w-1] - board[i+h-1][j-1] + board[i-1][j-1]);
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            scanf("%d",&board[i][j]);
            board[i][j]+=board[i][j-1]+board[i-1][j]-board[i-1][j-1];
        }
    }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            ans=max(ans,sol(i,j));
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1749.cpp