[SW Expert Academy] 2117. 홈 방범 서비스 C/C++ 풀이

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

 

시뮬레이션 문제.

문제만 처음 봤을 때는 전체 다 순회하려면 시간이 오래 걸릴 것이라고 생각했다.

근데 전체 MAP 크기가 20*20 밖에 안되고 각 포인트에서 다른 포인트까지의 거리(20*20)와 거리마다의 집 수를 기록해놓고 최대 집 개수와 비교했다.

 

결국 마름모 모양이라는 것은 시작점을 기준으로 (K=2)라면 거리 차이가 1 이하인 점들, (K=4)라면 거리 차이가 3 이하인 점들을 모아놓은 것이라서 한 점을 기준으로 거리마다의 집 수를 구하고 그를 이용해서 수익을 계산해주었다.

 

O(N^5)의 풀이가 나왔지만 최대 N이 20이라서 여유롭게 통과할 수 있었음.

 

아래는 코드

 

#include <cstdio>
#include <stdlib.h>
#include <string.h>

//INPUT이 길 경우 파일로 인풋을 받음
FILE* in = fopen("input.txt", "r");

int t, n, m;
int map[21][21];
int sol[39];
int max;
int max_house;

void cost(int a, int b) {
	//거리에 따른 집의 수*수익 초기화
	memset(sol, 0, sizeof(sol));
    //가장 멀리 있는 집의 거리가 얼마인지
	max = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
        	//거리에 따라 값 더해주기
			sol[abs(a-i) + abs(b - j)] += map[i][j];
       		//집이 있는 가장 먼 거리 갱신
			if (max < abs(a - i) + abs(b - j) && map[i][j] != 0)
			{
				max = abs(a - i) + abs(b - j);
			}
		}
	}
    //만약 최대 집 수가 0이고 기준점에 집이 존재한다면 최대 집 수를 1로 갱신
    //집 당 수익이 1 이상이기 때문에 (K=1)일 때 집이 존재한다면 무조건 손해가 아니다.
	if (map[a][b] > 0 && max_house == 0)
		max_house = 1;
   	//손해가 아닐 때 최대의 집 수를 갱신
	for (int i = 1; i <= max; i++)
	{
		sol[i] = sol[i] + sol[i - 1];
		if (sol[i] - (i * i + (i + 1) * (i + 1)) >= 0)
		{
			if (max_house < (sol[i] / m))
				max_house = sol[i] / m;
		}
	}
}

int main() {
	fscanf(in, "%d", &t);
	for (int i = 0; i < t; i++)
	{
		max_house = 0;
		fscanf(in, "%d %d", &n, &m);
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
				int a;
				fscanf(in, "%d", &a);
				map[j][k] = a * m;
			}
		}
        //MAP 상의 모든 점을 돌면서 최대 집 수 계산
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				cost(j, k);
		printf("#%d %d\n",i+1 ,max_house);
	}
	return 0;
}