SWEA 2001번: 파리 퇴치/DP

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq&categoryId=AV5PzOCKAigDFAUq&categoryType=CODE

SW Expert Academy

 

N과 M이 주어졌을 때

N*N배열에서, M*M의 부분합이 가장 큰 구간을 찾는 문제

부분합은 뭐다? DP다

 

그렇기 때문에 원래 배열의 값을 저장하는 array배열, (0,0)~(n,n)의 직사각형 합을 저장하는 sum배열 두 개를 선언했다

 

특정 좌표의 sum 값은

sum(i,j) = sum(i-1,j) + sum(i,j-1) - sum(i-1,j-1)로 구해줬다

 

직사각형 배열에서 어느 부분이 중복 계산될지 체크하면 풀 수 잇는 문제 !!

 

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            int ans=0;
            String s=sc.nextLine();
            int n=sc.nextInt(),m=sc.nextInt();
            int[][] arr=new int[20][20], sum=new int[20][20];

            for(int i=1;i<=n;i++) {
                for (int j = 1; j <= n; j++) {
                    arr[i][j] = sc.nextInt();

                    sum[i][j] = arr[i][j];
                    if (i > 0)
                        sum[i][j] += sum[i - 1][j];
                    if (j > 0)
                        sum[i][j] += sum[i][j - 1];
                    if (i > 0 && j > 0)
                        sum[i][j] -= sum[i - 1][j - 1];
                    //System.out.print(sum[i][j] + " ");
                }
                //System.out.println();
            }

            for(int i=0;i<=n-m;i++)
                for(int j=0;j<=n-m;j++){
                    int ss=sum[i+m][j+m]-sum[i][j+m]-sum[i+m][j]+sum[i][j];
                    if(ss>ans)
                        ans=ss;
                }

            System.out.println("#"+test_case+" "+ans);
        }
    }
}

Time Complexity: O(n²)