[이차원배열] SW Expert Academy 2001. 파리 퇴치 / 2차원 누적합

 

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq

SW Expert Academy

풀이

화려한 4중 for문을 보아하니 딱봐도 좋은 코드는 아니지만 일단 내가 푼 코드는

 

NxN크기의 판에 MxM의 파리채는 (N-M+1)^2가지 방법으로 들어갈수 있기 때문에 (N-M+1)^2 배열을 만들고 각각의 값을 구한후 max값을 찾는 방법으로 풀었다.

 

코드

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 N = sc.nextInt();
            int M = sc.nextInt();
            int len = N - M + 1;
            int[][] arr = new int[N][N];
            int[][] prefix = new int[len][len];
            int max = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }
            
            //영역별 값
            for(int i = 0; i < len; i++){
                for(int j = 0; j < len; j++){
                    for (int k = 0; k < M; k++){
                        for (int l = 0; l < M; l++){
                            prefix[i][j] += arr[i+k][j+l];
                        }
                    }

                }
            }
            
            //최댓값
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    if (prefix[i][j] > max) {
                        max = prefix[i][j];
                    }
                }
            }
            // 출력
            System.out.println("#" + test_case + " " + max);

        }
    }
}

 

코드비교

아무래도 내 코드가 너무 별로여서 지선생에게 너가 생각하는 최대 효율로 풀어달라고 해보았다.

지선생이 짜준 코드는 누적합 공식을 알아야지 이해할수 있는 코드인데 

누적합이 뭔지 이해하려면 아래 표를 보면 된다.

하나 예를 들어보자면 prefix[0][3] = arr[0][1] + arr[0][2] + arr[0][3] 인것을 볼수있다.

말그대로 이전 값을 현재 값에 더해서 누적 시킨것

---

✅ 예제 원본 배열 (arr)

예를 들어 다음과 같은 4×4 배열이 있다고 해봅시다:

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

 

---

✅ prefix[i][j] 계산 결과 (누적합 배열)

1	3	6	10
6	14	24	36
15	33	54	78
28	60	96	136

 

 

• 먼저 사용자로부터 테스트 케이스 개수 T를 입력받습니다.
• 각 테스트 케이스에 대해 다음의 작업을 수행합니다:
  • 정사각형 배열의 크기 N과 파리채의 크기 M을 입력받습니다.
  • (1,1)부터 (N,N)까지 사용할 수 있도록 크기가 N+1 x N+1인 2차원 배열 arr와 prefix를 선언합니다.
    • arr[i][j]는 (i,j) 위치에 존재하는 파리의 수를 저장합니다.
    • prefix[i][j]는 (1,1)부터 (i,j)까지의 사각형 영역에 존재하는 파리의 총 수를 저장할 배열입니다.
  • 다음으로, 배열에 파리 개수를 입력받으면서 동시에 누적합 배열 prefix를 계산합니다.
    • 이때 prefix[i][j]는 다음과 같이 계산됩니다:
      현재 위치의 파리 수 arr[i][j]에
      위쪽 누적합 prefix[i-1][j]와
      왼쪽 누적합 prefix[i][j-1]을 더하고,
      위쪽과 왼쪽이 겹치는 부분 prefix[i-1][j-1]은 한 번 빼줍니다.
  • 누적합 배열이 완성되면, 이제 실제로 파리채를 내리칠 수 있는 모든 위치에 대해 M x M 크기의 사각형 영역을 검사합니다.
    • 각 위치 (i,j)를 기준으로, 왼쪽 위 꼭짓점이 (i-M+1,j-M+1)이고 오른쪽 아래 꼭짓점이 (i,j)인 M x M 정사각형 영역의 파리 합을 구합니다.
    • 이 합은 누적합 배열을 이용해 O(1) 시간에 다음과 같이 계산됩니다:
      prefix[i][j] - prefix[i-M][j] - prefix[i][j-M] + prefix[i-M][j-M]
  • 그중 최대값을 갱신하여, 가장 많은 파리를 죽일 수 있는 경우를 기록합니다.
  • 마지막으로, 해당 테스트 케이스 번호와 함께 최대값을 출력합니다. 출력 형식은 #1 49처럼 #테스트번호 최대값입니다.

 

import java.util.Scanner;

class Solution {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 테스트 케이스 수 입력

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = sc.nextInt(); // 배열 크기 (N x N)
            int M = sc.nextInt(); // 파리채 크기 (M x M)

            // N x N 배열과 누적합 계산을 위한 배열 선언 (1-based index 사용)
            int[][] arr = new int[N + 1][N + 1]; 
            int[][] prefix = new int[N + 1][N + 1];

            // 배열 입력 및 동시에 2차원 누적합(prefix sum) 계산
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    arr[i][j] = sc.nextInt(); // (i, j) 위치의 파리 개수 입력

                    // (1,1)부터 (i,j)까지의 총 파리 수 계산
                    // 핵심 점화식: 현재 값 + 위 + 왼쪽 - 왼쪽 위 중복 영역
                    prefix[i][j] = arr[i][j] 
                                 + prefix[i - 1][j] 
                                 + prefix[i][j - 1] 
                                 - prefix[i - 1][j - 1];
                }
            }

            int maxFlies = 0; // 최대로 죽인 파리 수를 저장할 변수

            // 모든 가능한 M x M 영역을 확인하면서 최댓값 갱신
            for (int i = M; i <= N; i++) {
                for (int j = M; j <= N; j++) {
                    // (i-M+1, j-M+1) ~ (i, j) 범위의 M x M 구간 합을 구함
                    int total = prefix[i][j] 
                              - prefix[i - M][j] 
                              - prefix[i][j - M] 
                              + prefix[i - M][j - M];

                    // 최댓값 업데이트
                    if (total > maxFlies) maxFlies = total;
                }
            }

            // 결과 출력
            System.out.println("#" + test_case + " " + maxFlies);
        }
    }
}