SW 2001. 파리퇴치

SW Expert Academy

SW Expert Academy

M*M 배열을 만들고 그안에 숫자들 입력.

M*M크기 파리채로 내리쳤을 때 가장 큰 수 출력

 

어제 상당히 복잡하게 짰었던 것 같은데 다시 생각하면서 

간단하게 손코딩을 해봤다.

 

먼저 for문이 4중인데 겉에 2중은 배열의 범위 안 + 파리채로 갈 수 있는 최대의 좌표 ex) 5*5배열에 3*3파리채면 (2,2)가 최대로 시작할 수 있는 좌표

 

그리고 안에 for문 두 개는 겉 for문으로 정해진 좌표를 시작으로 파리채 넓이 M*M까지 돌면서 그 안의 값들을 더해주고 최댓값을 찾아내주는 역할.

 

여기서 처음에 고려 못 헀던 건 안for문 int k,m = 0;으로 했는데 이러면 좌표의 시작을 겉 for문으로 지정해놓은 의미가 없음.  i랑 j부터 시작을 해야하고 i와 j가 증가하면서 안 for문 2개의 조건식에도 더해줘야 파리채의 넓이만큼 더해갈 수 있따.

package algorithm;

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

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */
public class Solution
{
	public static void main(String args[]) throws Exception
	{
		//System.setIn(new FileInputStream("C:\\so_Project\\workspace\\BaekJoon\\src\\algorithm\\input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine()); //테스트 케이스의 수 
	
		for(int q=1;q<=num;q++) { //테스트 케이스만큼 반복
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int arr[][] = new int[N][N];
			
			for(int w=0;w<N;w++) { //배열에 파리 갯수 값 저장
				st = new StringTokenizer(br.readLine());
				for(int k=0;k<N;k++) 
						arr[w][k] = Integer.parseInt(st.nextToken());				
			}
			
			int max = 0; //잡는 파리의 최댓값
			for(int i =0;i<=N-M;i++) {
				for(int j = 0;j<=N-M;j++){
					int sum = 0;
					for(int k=i;k<i+M;k++) {
						for(int m=j;m<j+M;m++) {
							sum+= arr[k][m];
						}
					}
					if(max<sum)
						max = sum;
				}
			}
			System.out.println("#"+q+" "+max);
		}			
	}
}