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

문제

SWEA 모의 SW 역량테스트 - 2117 홈 방범 서비스

SW Expert Academy

 

---

문제 풀이

접근 방식

손해를 보지 않으면서 가장 많은 집을 포함하는 방범 서비스 영역에 포함된 집의 개수를 구하는 문제이다.

이를 구하기 위해 5중 for문을 돌며 최댓값을 구해주었다.

 

첫 번째 for문은 서비스 영역의 크기(k)를 나타낸다.

서비스 영역이 도시를 다 덮을 수 있을 만큼의 크기까지 확인해봐야 하기 때문에,

K = 1에서 K = N + 1의 크기까지 탐색해주었다. (풀이 코드에서 k = K - 1, 즉 k = 0에서 k = N까지 탐색)

 

두 번째와 세 번째 for문은 서비스 영역의 가운데 지점(i, j)을 의미한다.

 

네 번째와 다섯 번째 for문은 서비스 영역(a, b)을 의미한다.

아래와 같이 코드를 짜면 문제에서 주어진 모양의 영역을 탐색할 수 있다.

서비스 영역을 탐색하며 그 영역에 포함된 집의 개수를 구하였고,

이 값을 활용하여 손해를 보지 않는지 확인 후, 최댓값을 갱신해주었다.

for (a = i - k; a <= i + k; a++) {
	for (b = j - c ; b <= j + c; b++) {
		if (a < 0 || a >= N || b < 0 || b >= N) continue;
		if (map[a][b]) count++;
	}
	if (a < i) c++;
	else c--;
}
if (count * M - cost >= 0 && MAX < count) MAX = count;

 

---

풀이 코드 - C++

#include <iostream>
#include <cstring>
using namespace std;
 
int main(int argc, char** argv) {
    int test_case, i, j, k, a, b, c, cost, count, MAX;
    int T, N, M;
    bool map[20][20];
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        // 입력 받기
        cin >> N >> M;
        memset(map, 0, sizeof(map));
        for (i = 0; i < N; i++)  {
            for (j = 0; j < N; j++)  {
                cin >> map[i][j];
            }
        }
 
        // 최대 개수 구하기
        MAX = 0;
        for (k = 0; k <= N; k++) {
            cost = k * k + (k + 1) * (k + 1);   // 운영 비용
            for (i = 0; i < N; i++) {
                for (j = 0; j < N; j++) {
                    // 서비스 영역
                    c = 0;
                    count = 0;
                    for (a = i - k; a <= i + k; a++) {
                        for (b = j - c ; b <= j + c; b++) {
                            if (a < 0 || a >= N || b < 0 || b >= N) continue;
                            if (map[a][b]) count++;
                        }
                        if (a < i) c++;
                        else c--;
                    }
 
                    if (count * M - cost >= 0 && MAX < count) MAX = count;
                }
            }
        }
 
        cout << "#" << test_case << " " << MAX << '\n';
    }
    return 0;
}

실행 결과