SW 2117 홈 방범 서비스

제가 처음에 코딩할 때 마름모 모양으로 집 위치를 계산할 때 지도 밖의 부분(음수가 나오는 경우)를 거르기 위하여, 

  if (startX + i >= 0 && startX + i < N && startY +j >=0 && startY +j <N) {

....

}

로 조건을 달았었는대, 제가 구현한 마름모를 만드는 과정이

마름모 생성 기준점을 기준으로 +-i씩 체크하는 방법으로 구현하여서,

예를 들어서 N 10이고 마름모 생성 기준점이 (5.8)일 때 i가 3일 경우에 (5,5 6 7 8 9 )을 체크해야 하지만, i가 2일때 위의 조건에서 startY + j < N , 즉 8 + 2 < 10에 위배되어서 실제로는 (5, 7 8 9)만 탐색할 수 있었고 (5, 5 6)을 탐색할 수 없는 문제가 있었습니다.

이거를 못찾아서 몇시간동안 해맸었네요..

아랫부분은 해당 조건 부분을 수정하여서 잘 돌아갑니다.

/*

운영비용 = K * K + (K-1) * (K-1)

접근법 : 최대 수익이 문제가 아니므로 마름모를 큰거에서 작은거로 접근해보자!

1. 마름모의 크기 : '총 집수 * 지불하는 비용 >= 마름모의 비용' 을 만족하는 마름모의 크기로 시작하며 ,

집을 탐색한다.

1-1 해당 마름모로 탐색하면서 마름모 안에 들어가는 집의 최대 갯수가 가장 큰 경우를 출력하고 종료한다.

1-2 위의 조건을 만족하는 경우가 없는 경우 마름모의 크기를 하나 줄여서 1을 다시 시작한다.

*/

#include <cstdio>

using namespace std;

void createDiamond(int x, int y, int size);

int calSecurityCost(int k);

void init();

int T, N, M, ans;

int arr[22][22];

int main(void)

{

scanf("%d", &T);

for (int tc = 1; tc <= T; tc++){

int houseCnt = 0, possibleMaxCost=0, startKSize=1;

init();

scanf("%d %d", &N, &M);

for (int i = 0; i < N; i++){

for (int j = 0; j < N; j++){

scanf("%d", &arr[i][j]);

if (arr[i][j] == 1){

++houseCnt;

}

}

}

possibleMaxCost = houseCnt * M; //모든 집이 마름모에 들어간다 할 때, 집에서 낼 수 있는 최대 비용

////모든 집이 마름모에 들어간다 할 때, 가능한 마름모의 최대 크기 구하기

while (1){

if (calSecurityCost(startKSize) < possibleMaxCost){

startKSize++;

}

else{

startKSize--;

break;

}

}

//배열 각 부분좌표를 중심으로 삼아서 마름모를 만든다.

while (1){

for (int i = 0; i < N; i++){

for (int j = 0; j < N; j++){

createDiamond(i, j, startKSize);

}

}

//조건을 만족하는 경우가 있다면 최대 갯수를 출력하고 break;한다.

if (ans > 0){

printf("#%d %d\n", tc, ans);

break;

}

//조건을 만족하는 경우가 없다면 마름모의 크기를 1개 줄이고 함수를 다시 실행한다. 

startKSize--;

}

}

return 0;

}

int calSecurityCost(int k){

return k*k + (k - 1)*(k - 1);

}

void init(){

ans = 0;

}

void createDiamond(int x, int y, int size){

/*

중심좌표 좌우로 + size-1

상하로 1씩 변동하면 + size-1-i

*/

/*

시작은 중심 (x-(size-1), y)좌표에서 시작 하여 arr배열을 탐색하면서 집 수를 더한다.

더한 집 수 * 지불비용이 방범 서비스 비용보다 더 클경우 최댓값을 저장한다.

아니라면 아무값도 저장하지 않는다.

*/

int startX = x - (size - 1), startY = y;

int count = 1, check = 0;

for (int i = 0; i<(2 * size) - 1; i++){

for (int j = 0; j<count; j++){

//맵 밖으로 나가는 경우는 카운팅 하지 않는다.

if (startX + i >= 0 && startX + i < N){

//중심축이여서 한번만 실행될 경우

if (startY + j == startY){

if (arr[startX + i][startY + j] == 1)

check++;

}

//양옆 +-1 실행될 경우

else{

if (startY + j < N){

if (arr[startX + i][startY + j] == 1)

check++;

}

//음수 열은 체크하면 안된다.

if (startY - j >= 0){

if (arr[startX + i][startY - j] == 1)

check++;

}

}

}

}

//원래 중심 좌표로 왔다는건 이 점을 기준으로 양옆으로 탐색하는 칸 수를 1칸씩 줄여야 한다는 것

if (startX + i >= x){

count--;

}

else{

count++;

}

}

if (calSecurityCost(size) <= check * M){

ans = ans > check ? ans : check;

}

}