[SWEA-2001] 파리 퇴치

[누적합]-파리퇴치

SW Expert Academy

 

문제 설명

NxN 배열 안에 해당 영역에 존재하는 파리의 개수가 존재함.

이때, MxM 크기의 파리채를 한 번 내리쳐 최대한 파리를 죽이고자 할 때 죽은 파리의 개수 구하기

제약 사항

• N은 5 이상 15 이하
• M은 2 이상 N 이하
• 각 영역의 파리 개수는 30 이하

입출력 예시

N	M	arr	result
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]]	49

 

정답 예시

풀이 방법

2차원 배열 누적합 이용

 

1. 2차원 배열 누적합 구하기

	0	1	2	3	4
0	1	4	7	13	20
1	9	25	37	55	70
2	13	45	68	98	119
3	15	51	75	28	151
4	24	73	101	161	187

 

• 0행 → DP[0][c] = DP[0][c-1]+arr[0][c]
• 0열  → DP[r][0] = DP[r-1][0]+arr[r][0]
• 나머지 → DP[r][c] = DP[r-1][c] + DP[r][c-1] - DP[r-1][c-1] + arr[r][c]

2. MxM 크기의 부분합 구하기

	0	1	2	3	4
0	1	4	7	13	20
1	9	25	28	30	33
2	13	41	49	44	38
3	15	..	..	..	..
4	24	..	..	..	..

• r >= M-1 && c >= M-1 인 경우만 부분합 구하기
• 초기 max 값 = DP[M-1][M-1] = 25
• r-M < 0인 경우 → DP[r][c] - DP[r][c-M]
• c-M < 0인 경우 → DP[r][c] - DP[r-M][c]
• 나머지 → DP[r][c] - DP[r-M][c] - DP[r][c-M] + DP[r-M][c-M]

코드

import java.util.*;
import java.io.*;
import java.lang.*;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= T; test_case++)
		{
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // NxN 배열 크기
            int M = Integer.parseInt(st.nextToken()); // 파리채 크기
            
            int[][] arr = new int[N][N];
            // 배열 채우기
            for(int r=0; r<N; r++){
            	st = new StringTokenizer(br.readLine());
                int c = 0;
                while(st.hasMoreTokens()){
                	arr[r][c++] = Integer.parseInt(st.nextToken());
                }
            }
            
            int[][] dp = new int[N][N]; // 누적합
            dp[0][0] = arr[0][0]; // 0행 0열 값 설정
            // 0행 누적합
            for(int c=1; c<N; c++) dp[0][c] = dp[0][c-1] + arr[0][c];
            // 0열 누적합
            for(int r=1; r<N; r++) dp[r][0] = dp[r-1][0] + arr[r][0];
            // 나머지 누적합
            for(int r=1; r<N; r++){
            	for(int c=1; c<N; c++) {
                	dp[r][c] = dp[r-1][c] + dp[r][c-1] - dp[r-1][c-1] + arr[r][c];
                }
            }

			// MxM 크기만큼 부분합 구하기
            int max = dp[M-1][M-1]; // 초기 최댓값 설정
            for(int r=M-1; r<N; r++) {
            	for(int c=M-1; c<N; c++) {
                    int part_sum = 0; // 부분합
                	if(r==M-1 && c==M-1) continue;
                    else if(r-M < 0) {
                    	part_sum = dp[r][c] - dp[r][c-M];
                    }else if(c-M < 0) {
                    	part_sum = dp[r][c] - dp[r-M][c];
                    }else {
                    	part_sum = dp[r][c] - dp[r-M][c] - dp[r][c-M] + dp[r-M][c-M];
                    }
                    max = Math.max(max, part_sum); // 최댓값 갱신
                }
            }
            sb.append(String.format("#%d %d\n", test_case, max));
		}
        System.out.println(sb);
	}
}