SWExpertAcademy 2001번-파리 퇴치(JAVA)

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

SW Expert Academy

 

[제약 사항]

1. N 은 5 이상 15 이하이다.

2. M은 2 이상 N 이하이다.

3. 각 영역의 파리 갯수는 30 이하 이다.


[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,

다음 N 줄에 걸쳐 N x N 배열이 주어진다.


[출력]

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

 

import java.util.Scanner;

public class Solution {
	private static void fly(int max, int r, int c, int N, int M, int[][] arr, StringBuilder sb) {
		int sum = 0;
		if (r + M == N && c + M == N) {
			sb.append(max+"\n");
			return;
		}
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < M; j++) {
				sum += arr[r + i][c + j];
			}
		}
		if (max <= sum)
			max = sum;
		if (c + M == N)
			fly(max, r + 1, 0, N, M, arr, sb);
		else fly(max, r,c+1,N,M,arr, sb);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int T = sc.nextInt();
		int[][] arr;
		int N, M;
		for (int t = 0; t < T; t++) {
			N = sc.nextInt();
			M = sc.nextInt();
			arr = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j] = sc.nextInt();
				}
			}
			sb.append("#" + (t + 1) + " ");
			fly(0, 0, 0, N, M, arr, sb);
		}
		System.out.print(sb);
	}
}

현재 탐색중인 위치의 index와 max 값 등을 매개변수로 하는 재귀함수를 작성한 풀이법입니다.

현재 탐색중인 위치를 파리채의 좌상단 꼭짓점으로 간주하여 풀이하였습니다.

 

 

*fly(int max, int r, int c, int N, int M, int[][] arr, StringBuilder sb)

-매개변수

int max = 합계 최댓값

int r = 탐색 위치 row 

int c = 탐색 위치 column

int N = 배열의 크기 (N*N)

int M = 파리채의 크기(M*M)

int[][] arr = N*N 배열

StringBuilder sb = 결과 String 제작용 StringBuilder

 

-종료조건

//탐색위치가 더이상 오른쪽이나 아래로 움직일 수 없을 때 (탐색끝)

r + M == N && c + M == N

//결과 String에 max 값과 개행문자 저장하고 return

sb.append(max+"\n");
return;

 

-동작

//현재 위치에서 파리채의 면적만큼 합계 계산

for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
sum += arr[r + i][c + j];
}
}

//max 값보다 sum이 크거나 같다면 max를 sum값으로 갱신

if (max <= sum)
max = sum;

//column 탐색이 종료된 경우, [ r+1 ][ 0 ]로 재귀함수 호출

if (c + M == N)
fly(max, r + 1, 0, N, M, arr, sb);

//column 탐색이 종료되지 않은 경우, [ r ][ c+1 ]로 재귀함수 호출 
else fly(max, r,c+1,N,M,arr, sb);