동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점수 따먹기라는 게임인데 그다지 재밌어 보이지는 않는다.
동주가 개발한 게임은 이렇다. 일단 N*M 행렬을 그린 다음, 각 칸에 -10,000 이상 10,000 이하의 정수를 하나씩 쓴다. 그런 다음 그 행렬의 부분행렬을 그려 그 안에 적힌 정수의 합을 구하는 게임이다.
동주가 혼자 재밌게 놀던 중 지나가는 당신을 보고 당신을 붙잡고 게임을 하자고 한다. 귀찮은 당신은 정수의 합이 최대가 되는 부분행렬을 구하여 빨리 동주에게서 벗어나고 싶다.
입력
첫째 줄에 N (1 < N < 200), M (1 < M < 200)이 주어진다. 그 다음 N개의 줄에 M개씩 행렬의 원소가 주어진다.
출력
첫째 줄에 최대의 합을 출력하라.
예제 입력 1
3 5 2 3 -21 -22 -23 5 6 -22 -23 -25 -22 -23 4 10 2 |
예제 출력 1
16 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int N, M, **matrix=NULL, max=-10000;
scanf("%d%d", &N, &M);
matrix=(int **)malloc((N+1)*sizeof(int *));
for(int i=0;i<=N;i++)
matrix[i]=(int *)calloc(M+1,sizeof(int));
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
scanf("%d", &matrix[i][j]);
for(int i=0;i<=N;i++)
for(int j=1;j<=M;j++)
matrix[i][j]+=matrix[i][j-1];
for(int j=0;j<=M;j++)
for(int i=1;i<=N;i++)
matrix[i][j]+=matrix[i-1][j];
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
for(int k=0;k<i;k++)
for(int l=0;l<j;l++)
max=matrix[i][j]-matrix[k][j]-matrix[i][l]+matrix[k][l]>max?matrix[i][j]-matrix[k][j]-matrix[i][l]+matrix[k][l]:max;
printf("%d\n", max);
for(int i=0;i<=N;i++)
free(matrix[i]);
free(matrix);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 14369번: 전화번호 수수께끼 (Small) (0) | 2023.02.03 |
---|---|
<백준 알고리즘> 3584번: 가장 가까운 공통 조상 (0) | 2023.02.02 |
<백준 알고리즘> 3020번: 개똥벌레 (0) | 2023.02.02 |
<백준 알고리즘> 2580번: 스도쿠 (0) | 2023.02.02 |
<백준 알고리즘> 1759번: 암호 만들기 (0) | 2023.01.31 |