[1일차] 부분 배열의 합

- 문제 설명

크기가 N*N인 배열의 부분배열인 n*m 배열의 합충 가장 큰 값 출력

10<=N<=100, 1<=n,m<N

예시 5,2,3

ㅇㅇㅇㅁㅁ

ㅇㅇㅇㅁㅁ

ㅁㅁㅁㅁㅁ

ㅁㅁㅁㅁㅁ

ㅁㅁㅁㅁㅁ

동그라미로 표시된(2*3네모) 안에 있는 값들의 합을 비교

동그라미로 표시된 곳은 아래와 같이 이동 가능

ㅁㅁㅁㅁㅁ

ㅁㅁㅇㅇㅇ

ㅁㅁㅇㅇㅇ

ㅁㅁㅁㅁㅁ

ㅁㅁㅁㅁㅁ

결국 부분 배열로 가질 수 있는 합들을 다 비교해야함

- 입력

1 // 테스트 케이스

5 3 3 // N, n, m

0 1 1 0 1

1 1 0 1 1

0 1 1 0 0

0 0 1 0 0

1 0 1 0  0

- 출력

#1 6

- 입력 예시

2
5 3 3
0 1 1 0 1 
1 1 0 1 1 
0 1 1 0 0 
0 0 1 0 0 
1 0 1 0 0 
10 8 6
0 1 1 1 1 0 0 0 1 1 
1 1 1 1 1 0 1 0 1 1 
1 1 0 1 0 1 0 1 1 0 
1 0 0 1 1 1 0 1 0 1 
0 1 1 0 0 1 0 0 0 0 
1 1 1 0 1 1 0 1 0 1 
0 0 1 1 1 1 1 0 0 0 
1 1 0 0 1 0 1 0 1 1 
1 1 0 0 1 0 1 0 1 1 
1 1 0 1 0 0 1 1 0 0 

- 출력 예시

#1 6
#2 32

- 코드

int arr[100][100];

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        int N, row, col;

        scanf("%d %d %d",&N,&row,&col);

        for(int i=0; i< N; i++)

        {

            for(int j=0;j<N;j++)

            {

                scanf("%d",&arr[i][j]); // 입력받은 배열 채우기

            }

        }

        

        int maxSum = 0;

        

        for(int k=0;k<N-row+1;k++) // 행의 부분 배열

        {

            for(int r=0;r<N-col+1;r++) // 열의 부분 배열

            {

                int sum = 0;

                for(int i=k;i<row+k;i++) 

                {

                    for(int j=r;j<col+r;j++)

                    {

                        sum+=arr[i][j]; // 부분 배열 안의 합

                    }

                }

                if(sum > maxSum) maxSum = sum; // 최대값 저장

            }

        }

        printf("#%d %d\n",tc,maxSum);

    }

    return 0;

}