SW Expert Academy - 2001. 파리 퇴치 D2

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq&categoryId=AV5PzOCKAigDFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

문제에 앞서서 누적합이 무엇인지 알아보았다.

 

누적합 알고리즘 간단 설명

누적합은 배열에서 특정 구간의 합을 빠르게 구하려고 각 인덱스까지의 합을 미리 계산해 두는 알고리즘이다.
배열 값들을 누적해서 저장해 두고, 구간 합 계산할 때 바로 활용한다.

---

예제: 숫자 배열 [1, 2, 3, 4, 5]

배열의 각 인덱스까지의 합을 계산해서 누적합 배열 [1, 3, 6, 10, 15]을 만든다.
이걸 두 가지 방법으로 구할 수 있다.

---

첫 번째 방법: 단순 반복

각 인덱스까지의 값을 처음부터 더하면서 구한다.

• 1
• 1 + 2
• 1 + 2 + 3
• 1 + 2 + 3 + 4
• 1 + 2 + 3 + 4 + 5

이렇게 매번 처음부터 더하면 비효율적이다.

---

두 번째 방법: 이전 값 활용

이전까지의 누적합에 현재 값을 더해서 구한다.

• 1
• 1 + 2
• 3 + 3
• 6 + 4
• 10 + 5

이 방법은 이전 계산을 재활용하니까 훨씬 효율적이다.

---

누적합 정의

수열 AnA_nAn​에 대해 누적합 배열 SnS_nSn​을 만든다.

• 첫 번째 값은 그대로 둔다: S1=A1S_1 = A_1S1​=A1​.
• 이후에는 이전 누적합에 현재 값을 더한다: Si=Si−1+AiS_i = S_{i-1} + A_iSi​=Si−1​+Ai​.

누적합 배열을 만들어 놓으면 특정 구간 [A, B]의 합을 빠르게 구한다.

---

구간 합 계산

누적합 배열을 사용해서 배열의 특정 구간 [A, B]의 합을 구한다.

• Sum[A,B]=SB−SA−1Sum_{[A, B]} = S_B - S_{A-1}Sum[A,B]​=SB​−SA−1​.
• prefix[i+1][j+1]= arr[i][j]+prefix[i][j+1]+prefix[i+1][j]-prefix[i][j]; 코드로 이렇게 구현이 된다.

SBS_BSB​는 B번째 원소까지의 누적합이고, SA−1S_{A-1}SA−1​은 A-1번째 원소까지의 누적합이다.
이 두 값을 빼면 구간 [A, B]의 합을 빠르게 얻는다.

---

효율적인 이유

• 단순 반복 방식은 구간 길이가 길어질수록 연산량이 많아진다 (O(N)O(N)O(N)).
• 누적합 방식은 미리 계산한 값을 사용하니까 연산량이 거의 없다 (O(1)O(1)O(1)).

그래서 반복적으로 구간 합을 구할 때 누적합이 훨씬 유리하다.

---

어디에 쓰냐?

1. 배열에서 특정 구간의 합을 자주 구할 때 쓴다.
2. 2차원 배열에서 특정 영역의 합을 계산할 때 쓴다(2차원 누적합).
3. 데이터를 실시간으로 업데이트하면서 특정 구간 정보를 효율적으로 관리할 때 쓴다.

 

Code

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for(int t=1; t<=T; t++) {
			int N = sc.nextInt();
			int M = sc.nextInt();
			int [][] arr = new int[N][N];
			int [][] prefix = new int[N+1][N+1];
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					arr[i][j]=sc.nextInt();
					prefix[i+1][j+1]= arr[i][j]+prefix[i][j+1]+prefix[i+1][j]-prefix[i][j];
				}
			}
			int maxFiles=0;
			
			for(int i=M; i<=N; i++) {
				for(int j=M; j<=N; j++) {
					int files = prefix[i][j]-prefix[i-M][j]
							-prefix[i][j-M]+prefix[i-M][j-M];
					maxFiles = Math.max(maxFiles, files);
				}
			}
			
			System.out.printf("#%d %d\n", t, maxFiles);
		}
		sc.close();
	}
}