파리퇴치

해당 문제는 삼성 익스퍼트 아카데미에서 나온 파리퇴치 문제입니다.

해결 방식

브루트 포스 알고리즘을 바탕으로 코드를 작성하였습니다

해결 방식을 고른 이유

문제에서 제시하는 방식이 DP, BFS, DFS를 활용하지 않아도 충분히 풀 수 있다고 생각하였고,
위 알고리즘을 해결하여 작성하여도 수행속도가 크게 차이가 나지 않을것이라 판단하여
구현이 간단한 해결 방식을 골랐습니다.

코드

#include <iostream>
#include <stdlib.h>
using namespace std;

int		n;//배열의 크기
int		m;//파리채의 크기.
int**		list;
int		sol(int y, int x)
{
	int temp = 0;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < m; j++)
		{
			temp += list[y + i][x + j];
		}
	}
	return temp;
}

int main()
{
	int		big = 0;
	int		temp = 0;

	//벡터 초기화.
	cin >> n >> m;
	list = (int**)malloc(sizeof(int*) * n);
	for (int i = 0; i < n; i++)
		list[i] = (int*)malloc(sizeof(int) * n);
	int range = (n + 1) - m;//파리채의 범위 내에서 반복문을 돌기 위해 범위 설정
	for (int i = 0; i < range; i++)
	{
		for (int j = 0; j < range; j++)
		{
			temp = sol(i, j);
			if (big < temp)
				big = temp;
		}
	}
	cout << big << endl;
}

코드 해설

파리채로 파리가 가장 많이 있는 곳을 후려쳐, 죽인 수를 출력하는게 문제에서 요구하는 것입니다.
즉, 특정한 수가 아닌 최대 개수를 구하는 것이 목적이기에, 파리채의 범위를 벗어나는 구간은 탐색하지 않아도 됩니다.(가로세로 5칸의 배열, 2*2크기의 파리채의 경우, 배열의 5번째 칸을 시작으로 파리채를 후려치는 상황은 생각하지 않아도 된다는겁니다.)