2001 파리 퇴치

파리 퇴치 URL

내 풀이

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

public class SW2001 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st1.nextToken());
            int M = Integer.parseInt(st1.nextToken());

            int[][] graph = new int[N][N];

            for (int i = 0; i < N; i++) {
                StringTokenizer st2 = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    graph[i][j] = Integer.parseInt(st2.nextToken());
                }
            }
            int answer = 0;
            for (int i = 0; i <= N-M; i++) { //행
                for (int j = 0; j <= N-M; j++) { //열
                    int max = 0;
                    for (int k = i; k < i+M; k++) { //행
                        for (int l = j; l < j+M; l++) { //열
                            max += graph[k][l];
                        }
                    }
                    answer = Math.max(max, answer);
                }
            }
            System.out.println("#" + t + " " + answer);
        }
    }
}

배운점

시간이 오래 걸린 문제라 풀이를 다시 정리 해 보려고 한다.

어떻게하면 M * M 모양대로 반복할 수 있을까 고민하다가 오래전에 별찍기 하던게 생각이 났다. 원하는 모양대로 출력하는 별찍기.
그런식으로 접근했더니 금방 풀렸다.

풀이

1. 먼저 N-M까지 반복해야 모든 구역을 반복하며 더할 수 있다.
2. 열을 M만큼 반복하고 행동 M만틈만 반복해 준다.
3. Math.max() 함수로 최대값을 구한다.