[SWEA] 2117. [모의 SW 역량테스트] 홈 방범 서비스

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

SW Expert Academy

 

이 문제에서 k의 범위는 현재 좌표가 (x, y)라고 했을 때, 

k = |nx-x| + |ny-y|

를 이용해서 k의 범위를 만족하는 (nx, ny)를 구할 수 있다.

 

위의 식을 이용하여 모든 칸에서부터 모든 k의 범위 안에서 집의 수를 구한다.

문제에서 나오는 식을 이용하여 이익을 계산한 후에 손해가 아니라면(이익이 0 이상이라면) 최댓값과 비교한다.

 

#include <iostream>
#include <cmath>
using namespace std;
 
int n, m;
int maxcnt;
int map[20][20];
 
 
void solve(int x, int y) {
    int profit = 0;
 
    //k의 최댓값 n+2 까지 해본다.
    for (int k = 1; k < n+2; k++) {
 
 
        //k범위에 있는 집들을 모두 세준다.
        int homecnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int nx = abs(x - i);
                int ny = abs(y - j);
 
                //k범위 안에 있고 집이 있으면 집의 수 증가
                if (nx + ny < k && map[i][j] == 1) {
                    homecnt++;
                }
            }
        }
 
 
        //이익을 계산
        profit = m*homecnt - (k*k + (k - 1)*(k - 1));
        
        //손해가 아니라면 집의 수를 이전 집의 최대 값과 비교
        if (profit >= 0) {
            if (maxcnt < homecnt) maxcnt = homecnt;
        }
 
    }
}
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
 
    for (int tc = 1; tc <= T; tc++) {
        maxcnt = 0;
        cin >> n >> m;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
            }
        }
 
 
        //모든 칸에서 시작
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                solve(i, j);
            }
        }
 
        cout <<'#' << tc << ' ' <<  maxcnt << '\n';
    }
 
    return 0;
}