[JAVA] SWEA 2001 파리 퇴치

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq 

SW Expert Academy

 

1. 서론

 

배열을 탐색하는 문제. 얼마 전에 풀었던 '어디에 단어가 들어갈 수 있을까' 문제와 비슷하게 풀 수 있다. (근데 그게 훨씬 어려움)

 

https://coding-log.tistory.com/154?category=954740 

[JAVA] SWEA 1979 어디에 단어가 들어갈 수 있을까

 

2. 문제 풀이

 

N x N의 배열이 있다. 이 배열에서 M x M의 범위의 합이 가장 큰 값을 구하는 문제이다.

범위를 어떻게 설정한는지가 이 문제를 푸는 핵심이다.

특히 위의 문제처럼 그냥 i, j를 범위대로 for문으로 일정한 값을 그냥 돌리는 게 아니고 i값과 j값이 조건에 따라 따로 움직여야 한다.

 

그림을 그려서 범위를 이해하는게 가장 빨랐다. input 예제 기준으로 7x7 짜리 배열에서 5x5로 값을 구할 때

 

0, 0 ~ 4, 4

0, 1 ~ 4, 5

0, 2 ~ 4, 6

...

 

이런 식으로 배열의 범위가 이동한다. 그렇다면 이제 범위 밖을 벗어나게 되는데 i, j의 값을 어떻게 바꿔야 할까?

j의 값이 n이되면 i값이 +1이 되게 하면 되는 것이다.

 

3. 코드 설명

 

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		
		int t = s.nextInt();
		
		for (int k = 0; k < t; k++)
		{
			int n = s.nextInt(), m = s.nextInt();
			
			int[][] a = new int[n][n];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					a[i][j] = s.nextInt();
			
			int max = 0, x = 0, y = 0;
			while(true)
			{
				int sum = 0;
				for (int i = x; i < m + x; i++)
					for (int j = y; j < m + y; j++)
						sum += a[i][j];
				max = Math.max(max, sum);
				y++;
				if (y + m > n) {
					x++; 
					y = 0;
				}
				if (x > n - m) break;
			}
			
			System.out.println("#" + (k + 1) + " " + max);	
		}
	}
}

 

x, y를 따로 지정해줘서 범위를 조절했다. x부터 ~ m + x까지, 즉 범위는 이동하면서 MxM 범위를 돌도록 하는 것이다.

그리고 max함수를 써서 값을 계속 갱신해줬다.

y값이 배열의 경곗값에 가면 다시 0으로 돌리고 x값을 밑으로 옮겨준다. 그리고 배열을 다 돌 때까지 반복한다.