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

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

SW Expert Academy

꽤나 쉬운 문제

이제 삼성 코테가 2주도 안 남은 상황이당

마지막으로 봤던 역량테스트가 꽤나 어려운 난이도였기 때문에 문제풀이 연습에 좀 더 신경을 쓰게된당

(로봇이 작물 심고 열리고 수확하고 이런 문제였는데 내 주변에서 풀었던 사람이 나밖에 없었음)

 

 

서비스 영역의 크기가 K와 같을때 방범 서비스의 영역이다

영역의 크기는 2K^2 - 2K + 1과 같다

한 집 당 M의 방범 비용을 지불 가능할 때, 손해를 보지 않으면서 가장 많은 집을 케어할 수 있는 경우를 찾는 문제

보이겠지만, 수도코드가 굉장히 짧다

k의 범위는 최대 수금(?) 가능한 비용보다 운영 비용이 커질 때 종료한다

for문 내에서 거리가 K이하인 집들을 count해서 최대값을 계속 갱신해주면 끝

#include <cstdio>
#include <math.h>
int tc, n, m, map[21][21];
int cost(int k) { return 2 * k * k - 2 * k + 1; }
bool safe(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
int main() {
	scanf("%d", &tc);
	for (int T = 1; T <= tc; T++) {
		int ans = 1, h = 0, k = 2;
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				scanf("%d", &map[i][j]);
				if (map[i][j])h++;
			}

		while (h * m >= cost(k)) {
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++) {
					int sum = 0;
					for (int a = i - k; a <= i + k; a++)
						for (int b = j - k; b <= j + k; b++) {
							if (!safe(b, a))continue;
							if (abs(a - i) + abs(b - j) < k
								&& map[a][b])
								sum++;
						}
					if (sum * m >= cost(k)
						&& sum > ans)
						ans = sum;
				}
			k++;
		}
		printf("#%d %d\n", T, ans);
	}
	return 0;
}

answer의 최소값은 1이라는걸 체크 안 해줘서 첫트에는 틀렸다 ㅠ

테스트 케이스는 항상 경계값 체크해주는거 잊지 말기 😉