static int N, M;
static int board[20][20];
static int d[2][2] = {
-1, 0, //up
1, 0 //down
};
typedef struct
{
int y, x, len;
}info;
static bool out_of_bound(int y, int x)
{
if (y < 0 || y >= N)
return true;
if (x < 0 || x >= N)
return true;
return false;
}
static int get_home(int k, int y, int x)
{
int ret = 0, len = 2 * k - 1;
queue<info> q;
q.push({ y, x, len }); //중심,
len -= 2;
for (int i = 1; i < k; i++) //양 옆으로,
{
if (x - i >= 0)
q.push({ y, x - i, len });
if (x + i < N)
q.push({ y, x + i, len });
len -= 2;
}
while (q.size())
{
info t = q.front();
q.pop();
y = t.y; x = t.x;
len = t.len;
if (board[y][x]) //center
ret += 1;
for (int dir = 0; dir < 2; dir++) //위, 아래로
{
int cy = y;
int cx = x;
for (int c = 0; c < len / 2; c++) //절반의 길이 만큼,
{
cy += d[dir][0];
cx += d[dir][1];
if (out_of_bound(cy, cx))
break;
if (board[cy][cx])
ret += 1;
}
}
}
return ret;
}
static int solution(void)
{
int home = 0, ret = 1, profit;
scanf("%d %d", &N, &M);
for (int y = 0; y < N; y++)
{
for (int x = 0; x < N; x++)
{
scanf("%d", &board[y][x]);
home += board[y][x];
}
}
for (int k = 2; k < N; k++)
{
int operation = k * k + (k - 1)*(k - 1);
for (int y = 0; y < N; y++)
{
for (int x = 0; x < N; x++)
{
int cnt = get_home(k, y, x);
profit = cnt * M - operation;
if (profit >= 0 && cnt > ret) //**손해를 보지 않고, 많은 집에 서비스 제공,
ret = cnt;
}
}
}
profit = (home * M) - (N * N + (N - 1)*(N - 1));
if (profit >= 0) //손해를 보지 않음,
ret = home;
return ret;
}"손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾고,
그 때의 홈방범 서비스를 제공 받는 집들의 수" 를 구해야 한다.
문제를 제대로 읽지 않아 이익의 최대값을 구하고 있었다.
풀이는 다음과 같이 하였다.
먼저, k==1 인 경우는 따로 계산할 필요가 없다. 최대 1개의 집만 서비스를 이용할 수 있기 때문이다.
그 다음 k >= 2 인 경우에는 직접 계산해보아야 한다.
방범 서비스 영역의 중심을 배열 전체에 적용해보고, 그 때 손해가 없는지 확인하고 그 때 서비스를 집의 개수가 최대인지 확인하면 된다.
여기서 손해가 없다는 것은 이윤이 적어도 음수가 아니라는 것을 말한다.
그래서 profit >= 0 이 되는 것이다.
다음은 서비스 영역을 설정하였을 때, 해당 서비스를 이용할 수 있는 집의 개수를 세는 방법이다.
예를 들어 설명하면, k == 4 일 때는 아래와 같이 서비스 영역이 설정된다.
여기서 알 수 있는 것은 k==n 일 때, 가장 긴 라인은 2k - 1 의 길이를 갖고, 그 양옆으로는 2 만큼 길이가 줄어든다는 것이다.
그리고 가운데 행은 중심 축으로서 위, 아래로 움직이는 시작점으로 사용하였다.
그래서 코드에서 먼저 중심 좌표에 대해 먼저 확인하고, 위, 아래로 움직이면서 집이 있는지 확인 하는 것이다.
마지막은 k == N 일 때에 대한 것이다.
짝수에 대해서는 k == N 으로 배열 전체를 감쌀 수 없다.
그러나 홀수에 대해서는 k == N 이 되면 배열 전체를 감싸게 된다.
이러한 이유는 열의 길이가 홀수이기 때문이다.
생각해보니 solution() 에서 마지막 부분이 좀 에러라, 이러한 부분에 대한 예외처리가 필요 할 것 같다.
