파리 퇴치 (D2)

문제 링크

• N*N 정사각형 배열 안에 M*M 사이즈 정사각형의 수가 가장 큰 값을 찾는 문제
• 당연히 N > M
• for 문을 4개 돌려서 쉽게 풀 수 있었지만,,
• 그렇게 풀기 싫어서 이것저것 생각하다가 엄청 오래 푼 문제,,,
• 결국 생각해낸 방법은 (0,0)~(M,M)의 파리채로 잡을 수 있는 파리수 초기화(start라고 정의)하여
  • j를 한칸씩 이동하며 오른쪽 한줄을 더해주고 왼쪽 한줄을 빼주며 max값 업데이트하기
  • j를 한칸씩 이동하며 오른쪽 한줄을 더해주고 왼쪽 한줄을 빼주며 max값 업데이트하기
  • i를 한칸씩 이동할때는 start 값에 아래 한줄을 더해주고 위의 한줄을 빼준다
  • 다시 j 이동
• 위의 순서를 반복해주며 max 값을 갱신해줬다.

4중 for문

int maxSum = 0;
for (int i = 0; i <= N - M; i++) {
	for (int j = 0; j <= N - M; j++) {
		int sum = 0;
		for (int x = 0; x < M; x++) {
			for (int y = 0; y < M; y++) {
				sum += map[i + x][j + y];
			}
		}
		maxSum = Math.max(sum, maxSum);
	}
}

이렇게 for문을 4개쓰면 입력받고 max찾고 쉽게 끝나지만,, 이렇게 왜 하기가 싫었는지 나도 모르겠다
문제를 어렵게 푸는 병이 있나,,,

Solution

package swea;

import java.util.Scanner;

// 파리 퇴치
public class p2001 {
	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(); // 영역 N*N
			int M = sc.nextInt(); // 파리채 사이즈 M*M

			int[][] map = new int[N][N]; // N*N 배열 생성
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
				}
			} // 입력 for

			int start = 0; // 첫 파리채 값
			for (int i = 0; i < M; i++) {
				for (int j = 0; j < M; j++) {
					start += map[i][j];
				}
			} // (0,0)~(M,M)의 파리채로 잡을 수 있는 파리수 초기화

			int maxSum = start; // 파리채가 내려쳐서 죽일 수 있는 가장 큰 값, ans
			for (int i = 0; i < N - M + 1; i++) {
				int sum = start; // 오른쪽으로 한칸씩 이동할 때 사용할 sum
				for (int j = 0; j < N - M; j++) {
					for (int k = 0; k < M; k++) {
						sum += map[i + k][j + M]; // 오른쪽으로 한칸 이동해서 파리채 영역으로 들어온 값 더해주고
						sum -= map[i + k][j]; // 이동해서 파리채 영역 밖으로 나가게 된 값 빼주고
					}
					maxSum = Math.max(maxSum, sum);
				}
				if (i < N - M) { // 마지막 i일때는 다음 칸 없으므로 그 전까지만
					for (int k = 0; k < M; k++) {
						start += map[i + M][k]; // 아래로 한칸 이동해서 파리채 영역으로 들어온 값 더해주고
						start -= map[i][k]; // 이동해서 파리채 영역 밖으로 나가게 된 값 뺴주고
					}
				}
				maxSum = Math.max(maxSum, start);
			} // 파리채 이동 for

			System.out.printf("#%d %d\n", t, maxSum);
		} // testcase for
	}
}