SWEA 2001번: 파리 퇴치

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다. 아래는 N=5 의 예이다.   M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다. 죽은 파리의 개수를 구하라! 예를 들어 M=2 일 경우 위 예제의 정답은 49마리가 된다.   [제약 사항] 1. N 은 5 이상 15 이하이다. 2. M은 2 이상 N 이하이다. 3. 각 영역의 파리 갯수는 30 이하 이다. [입력] 가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고, 다음 N 줄에 걸쳐 N x N 배열이 주어진다. [출력] 출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다. (t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

prefix sum algorithm을 이용한 결과 코드

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 15
#define COMPARE(x, y)( x>y?x:y)
//using prefix sum algorithm
int main() {
	int N, M, T;
	int i, j, k;
	int max = 0, fly_num = 0;;
	int matrix[MAXSIZE][MAXSIZE] = { 0, };
	int presum[MAXSIZE + 1][MAXSIZE + 1] = { 0, };

	scanf("%d", &T);

	for (i = 0; i < T; i++) {
		scanf("%d %d", &N, &M);
		//construct N*N matrix
		for (j = 0; j < N; j++)
			for (k = 0; k < N; k++)
				scanf("%d", &matrix[j][k]);

		//construct (N+1)*(N+1) prefix sum matrix
		for (j = 0; j < N; j++) {
			for (k = 0; k < N; k++) {
				presum[j + 1][k + 1] = presum[j + 1][k] + presum[j][k + 1] + matrix[j][k] - presum[j][k];
			}
		}

		//find number of flies
		for (j = M; j < N + 1; j++) {
			for (k = M; k < N + 1; k++) {
				fly_num = presum[j][k] - presum[j - M][k] - presum[j][k - M] + presum[j - M][k - M];
				max = COMPARE(max, fly_num);
			}
		}
		printf("#%d %d\n", i + 1, max);
		max = 0;
	}
	return 0;
}

 

prefix sum alogrithm 채점 결과

무식하게 brute force 방식으로 구한 결과코드

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 15
#define COMPARE(x, y)( x>y?x:y)
//using prefix sum algorithm
int main() {
	int N, M, T;
	int i,j,k,l,m;
	int max = 0, fly_num = 0;
	int matrix[MAXSIZE][MAXSIZE] = { 0, };
	int presum[MAXSIZE + 1][MAXSIZE + 1] = { 0, };

	scanf("%d", &T);

	for (i = 0; i < T; i++) {
		scanf("%d %d", &N, &M);
		//construct N*N matrix
		for (j = 0; j < N; j++)
			for (k = 0; k < N; k++)
				scanf("%d", &matrix[j][k]);

		for (j = 0; j <= N-M; j++) {
			for (k = 0; k <= N-M; k++) {
				for (l = 0; l < M; l++) {
					for (m = 0; m < M; m++) {
						fly_num += matrix[l + j][m + k];
					}
				}

				max = COMPARE(max, fly_num);
				fly_num = 0;
			}
		}
		printf("#%d %d\n", i+1, max);
		max = 0;
	}
	return 0;
}

brute force 채점 결과

 

둘의 채점 결과 차이가 크지 않은데, 이는 배열의 크기가 작아서 그런 듯 합니다.

아무래도 배열 크기가 커질수록 prefix sum algorithm을 이용한 방식이 훨씬 효율적이겠죠!