코드트리 [자바 java] 정수 n개의 합 3

https://www.codetree.ai/missions/8/problems/sum-of-n-integers-3?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 정수 n개의 합2 문제의 2차원배열 버전이다.

https://ethereal-coder.tistory.com/127

코드트리 [자바 java] 정수 n개의 합 2

 

이 문제 역시 부분합을 사용한다.

 

이러한 배열이 있고, (a,b)에서 (c,d) 만큼 더한 값을 구하라고 했다고 하자.

 

 

 

위 배열이 부분합이다. 각각의 인덱스는 (0,0)에서 해당 인덱스까지의 합을 의미한다. 각각의 부분합을 구하는 점화식은 

부분합[i][j] = 부분합[i-1][j] + 부분합[i][j-1] - 부분합 [i-1][j-1] + 배열[i][j] 이다. 

부분합[i-1][j] + 부분합[i][j-1] 을 해서 중복되는 부분인 부분합[i-1][j-1]은 뺀다. 여기서 원하는 곳의 합을 구하는 방법은 

 

부분합이 arr이라고 하고, (x1,y1)에서 (x2,y2)의 합을 구한다고 했을 때

arr[x2][y2] - arr[x1-1][y2] - arr[x2][y1-1] + arr[x1][y2]를 하면 된다.

여기서도 arr[x1-1][y2] - arr[x2][y1-1] 를 하는 과정에서 중복으로 빠진 부분을 + arr[x1][y2]로 채웠다.

 

이 문제에서는 k*k만큼의 사각형에 들어오는 값의 합 중 가장 큰 값을 고르라고 했으니. (i,j)에서 (i+k,j+k)까지의 합을 모두 구해서 값을 출력했다.

import java.io.*;
import java.util.*;
import java.math.*;


public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        k--;

        int[][] arr = new int[n+1][n+1];

        for(int i = 1;i<=n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1;j<=n;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] hap = new int[n+1][n+1];//부분합

        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                hap[i][j] = arr[i][j] + hap[i-1][j] + hap[i][j-1] - hap[i-1][j-1];
                //부분합 배열 채우기(0,0)에서 해당 배열까지의 합을 의미
            }
        }

        // for(int i = 1;i<=n;i++){
        //     System.out.println();
        //     for(int j = 1;j<=n;j++){
        //         //System.out.printf("%d ",hap[i][j]);
        //     }
        // }

        int max = 0;

        for(int i = 1;i<=n-k;i++){
            for(int j = 1;j<=n-k;j++){
                //(i,j)에서 (i+2,j+2)
                int now = hap[i+k][j+k] - hap[i-1][j+k] - hap[i+k][j-1] + hap[i-1][j-1];
                max = Math.max(max, now);
               // System.out.println(now);
                //k*k만큼의 부분배열의 합을 구해 최댓값과 비교
            }
        }

        System.out.println(max);

        
    }
}