[SWEA] - 2001 : 파리퇴치1 - Java

문제

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다.

아래는 N=5 의 예이다.

M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다.

죽은 파리의 개수를 구하라!

예를 들어 M=2 일 경우 위 예제의 정답은 49마리가 된다.

[제약 사항]

1. N 은 5 이상 15 이하이다.

2. M은 2 이상 N 이하이다.

3. 각 영역의 파리 갯수는 30 이하 이다.

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,

다음 N 줄에 걸쳐 N x N 배열이 주어진다.

[출력]

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.sql.SQLOutput;
import java.util.StringTokenizer;


public class Main {
    static StringTokenizer st;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] g;
    static int T;
    static int n, m;
    static int res = Integer.MIN_VALUE;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            g = new int[n+1][n+1];
            // 입력과 동시에 누적합 저장.
            for (int i = 1; i <= n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 1; j <= n; j++) {
                    g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + Integer.parseInt(st.nextToken());// 현재위치까지 더해줌.
                }
            }

            res = Integer.MIN_VALUE;
            sb = new StringBuilder();
            cal();
            sb.append("#").append(t).append(" ").append(res);
            System.out.println(sb);
        }
    }

    public static void cal() {
        for (int i = m; i <= n; i++) {
            for (int j = m; j <= n; j++) {
                int sum = g[i][j] - g[i - m][j] - g[i][j - m] + g[i - m][j - m];
                res = Math.max(res, sum);
            }
        }
    }



}

코멘트

2차원 배열 누적합. 어디서든 적용 가능.