SWEA_D2_2001

📁 [D2_2001] 파리 퇴치

import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			int N = sc.nextInt();
			int M = sc.nextInt();

			// 입력
			int[][] arr = new int[N][N];

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j] = sc.nextInt();
				}
			}

			int max = 0;

			// 탐색
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					
					int sum = 0;
					
					// M*M 파리채 탐색
					for (int a = 0; a < M; a++) {
						for (int b = 0; b < M; b++) {

							int nx, ny;
							nx = j + b;
							ny = i + a;

							// 범위 넘어가면 중지
							if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
								break;
							} else {
								sum += arr[ny][nx];
							}
						}
					}
					
					// 최댓값 구하기
					max = Math.max(max, sum);
				}
			}

			// 출력
			System.out.println("#" + tc + " " + max);

		}
	}
}

🤔 나의 생각

처음에 TestCase만 보고 3방향으로 가야지 하고 신나서 했는데..
바보였다.. ㅋㅋㅋ 문제를 자세히 안 읽은 바보..
그래서 방향탐색보다 차라리 이중 for문으로 파리채를 탐색하자고 했다.
사실 풀기는 했지만 시간 복잡도가 어마무시 할 것 같다.. O(n^4) 인가..?
이건 망한거다 캬캬컄 나중에 다른 코드 참고해서 한 번더 확인해 봐야겠다.