[JAVA] SWEA 2001 파리잡기 (누적합)

Kyungmin·2023년 11월 9일

JAVA알고리즘

목록 보기

13/23

📝 문제 - 파리잡기-D2

// 파리퇴치 //

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class D2_2001 {

    // 원본 배열
    static int[][] map;

    // 누적합을 저장하기 위한 배열
    static int[][] sumMap;
    static int T,N,M;
    static int solution(int[][] map,int m) {

        // 누적합을 저장해 놓기 위한 배열에 저장
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                sumMap[i][j] = map[i-1][j-1] + sumMap[i-1][j] + sumMap[i][j-1] - sumMap[i-1][j-1];

            }
        }
        int maxSum = Integer.MIN_VALUE;

        for(int i=M; i<=N; i++) {
            for(int j=M; j<=N; j++) {
                int sum = sumMap[i][j] - sumMap[i][j-M] - sumMap[i-M][j] + sumMap[i-M][j-M];
                maxSum = Math.max(sum,maxSum);
            }
        }
        return maxSum;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // 테스트 케이스
        T = Integer.parseInt(bf.readLine());
        // #1 부터 시작함
        int testCase = 1;
        while (testCase <= T) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            // n x n 배열
            N = Integer.parseInt(st.nextToken());
            // m x m 배열 => 파리를 잡을 배열
            M = Integer.parseInt(st.nextToken());
            map = new int[N][N];
            // 누적합 배열
            sumMap = new int[N + 1][N + 1];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(bf.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            System.out.println("#"+testCase+ " "+ solution(map, M));
            testCase ++;
        }
    } // while 문 종료
}

<입력>
2
5 2
1 3 3 6 7
8 13 9 12 8
4 16 11 12 6
2 4 1 23 2
9 13 4 7 3
6 3
29 21 26 9 5 8
21 19 8 0 21 19
9 24 2 11 4 24
19 29 1 0 21 19
10 29 6 18 4 3
29 11 15 3 3 29
<출력>
#1 49
#2 159

문제 자체는 간단하다.
첫 번째 줄에 T(테스트케이스) 를 입력하고, 두 번째 줄에 2차원배열 N , 누적합을 구할 M 크기의 배열 M 을 입력하고 세 번째 줄에 N 배열을 입력한다.

✅ 접근

Prefix Sum(누적합) 을 이용하여 합을 저장해놓은 [N+1][N+1] 배열을 만들었다.
배열의 크기를 N+1로 하는 주 이유는 누적 합(Prefix Sum) 배열을 계산할 때 인덱스를 1부터 시작하기 위함이다. 이렇게 함으로써 경계 조건 처리를 간단하게 할 수 있으며, 특히 누적 합을 계산할 때 범위 밖의 값(0번 인덱스)을 기본값(0)으로 사용할 수 있다.

업로드중..

예를 들어 4 x 4 크기의 Map 배열이 있고, 누적합을 구하기 위한 5 x 5 크기의 sumMap 배열이 있다고 하자.

📝 누적합 배열(sumMap)

// 누적합을 저장해 놓기 위한 배열에 저장
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                sumMap[i][j] = map[i-1][j-1] + sumMap[i-1][j] + sumMap[i][j-1] - sumMap[i-1][j-1];
     }
  }

인덱스 번호는 1부터 시작한다. 그림과 같이 sum[1][1] 부터 저장을 하는데,

sumMap[i][j] = Map[i-1][j-1] + sumMap[i-1][j] + sumMap[i][j-1] - sumMap[i-1][j-1];

만약 Map[1][1] "까지" 의 2 x 2 크기 누적합(1+2+2+3 = 8) 을 구하고 싶다면,
Map[1][1] + sumMap[1][2] + sumMap[2][1] - sumMap[1][1] ,
즉 3 + 3 + 3 - 1 = 8 와 같은 방법으로 누적합을 저장한다.

📝 range sum(원하는 배열크기의 합) 구하기

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

반복문의 시작은 M이다.
이 부분은 그냥 공식처럼 암기하기로 했다.

그림에서와 같이