[D2] 파리퇴치 - 구간 합

1.  💎 문제

SW Expert Academy

 

 

---

 

 

2.  🤔어떻게 풀까?

이거는 다 더해봐야 풀 수 있겠다고 생각하다가 어떻게 하면 로직을 줄일 수 있을까 고민했다. 결국 구간합을 이용하기로 했다! 

구간합을 이용하여 O(n)으로 문제를 풀 수 있다. 만약 구간합을 미리 구하지 않는다면 모든 순서마다 요소들을 구해 더해줘야 하므로 O(M*N)으로 오랜 시간이 걸린다.

 

 

 

3.  💡 풀이 로직

1. 숫자 입력 받기 & 구간 합 구하기

현재 요소의 구간 합은 `sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + nums[i][j]`로 구한다.

		String [] data = br.readLine().split(" ");
            int N = Integer.parseInt(data[0]);
            int M = Integer.parseInt(data[1]);

            int [][]nums = new int[N+1][N+1];
            int [][] sum = new int[N+1][N+1];

            // 숫자 데이터 입력받기
            for(int i=1; i<=N;i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int j=1; j<=N; j++){
                    nums[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            // 구간 합 구하기
            for(int i=1; i<=N; i++){
                for(int j=1; j<=N; j++){
                    sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + nums[i][j];
                }
            }

 

 

 

2. M X M 크기의 구간 합 중 최대를 찾는다.

루프를 돌면서 하나하나 찾아야 한다. 이때 M X M 크기의 구간 합을 찾기 위해서, 미리 구한 구간 합을 이용한다.

`sum[i][j] - sum[i-M][j] - sum[i][j-M] + sum[i-M][j-M]`으로 부분 합을 구하고 제일 큰 부분 합을 출력한다.

	int max = Integer.MIN_VALUE;
            for(int i=M; i<=N; i++){
                for(int j=M; j<=N; j++){
                    int partSum = sum[i][j] - sum[i-M][j] - sum[i][j-M] + sum[i-M][j-M];
                    max = Math.max(partSum, max);
                }
            }

 

 

 

 

4.  🖥️ 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

class Solution
{
    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T;
        T= Integer.parseInt(br.readLine());

        for(int test_case = 1; test_case <= T; test_case++)
        {
            String [] data = br.readLine().split(" ");
            int N = Integer.parseInt(data[0]);
            int M = Integer.parseInt(data[1]);

            int [][]nums = new int[N+1][N+1];
            int [][] sum = new int[N+1][N+1];

            // 숫자 데이터 입력받기
            for(int i=1; i<=N;i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int j=1; j<=N; j++){
                    nums[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            // 구간 합 구하기
            for(int i=1; i<=N; i++){
                for(int j=1; j<=N; j++){
                    sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + nums[i][j];
                }
            }

            int max = Integer.MIN_VALUE;
            for(int i=M; i<=N; i++){
                for(int j=M; j<=N; j++){
                    int partSum = sum[i][j] - sum[i-M][j] - sum[i][j-M] + sum[i-M][j-M];
                    max = Math.max(partSum, max);
                }
            }
            bw.write("#" + test_case + " " + max +"\n");
        }

        bw.flush();

        bw.close();
        br.close();

    }
}