[SW Expert Academy] 2117. [모의 SW 역량테스트] 홈 방범 서비스 풀이 (C++)

2017. 10. 16에 쓰여진 글입니다.

---

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu&categoryId=AV5V61LqAf8DFAWu&categoryType=CODE

SW Expert Academy

 

풀이방법

이것도 완탐.. 그냥 모든좌표에서 k를 증가시켜가면서 비용을 측정해보면됨.

이때 k를 어디까지 증가시킬지가 문제인데 주어진 N크기의 맵을 담을수있는 크기 까지 증가시키면됨

모든 맵을 k가 N+1이 되면 맵이 무조건 담김.

N의크기가 2라고하면 k가3. 즉 밑에와 같은 상태에서 맵이 담기는것임.

 

이런식으로..

N이 10이면 K는 N+1 즉 K=11인 상태에서 10크기의 맵이 저 영역안에 잠기게됨. (궁금하면해보세요)

무튼 이렇게 해서 다찾아주면 끝남.그럼 K가 1인 상태부터 모든 맵이 K구역안에 잠긴상태까지 완탐을 돌게될것임.

그렇게 해서 풀어주면 끄읕~

 

소스코드

#include <iostream>
#include <algorithm>

using namespace std;

enum { EMPTY = 0, HOME = 1 };
int Answer;
int map[20][20];
int N, M;
int price[22] = { 0 };
int home_count;
int dx[] = { 1,1,-1,-1 };
int dy[] = { 1,-1,-1,1 };

void Init_map()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			map[i][j] = EMPTY;
}

void solve(int cur_x,int cur_y,int k)
{
	if (map[cur_x][cur_y] == HOME)
		home_count++;
	for (int i = 1; i < k; i++) {		//k-1번반복
		cur_x--;		//돌릴좌표 위로 이동
		for (int j = 0; j < 4; j++) {		//대각선시계방향으로 회전하기
			for (int m = 0; m < i; m++) {
				if (0 <= cur_x+dx[j]&& cur_x + dx[j] < N && 0 <= cur_y + dy[j] && cur_y + dy[j] < N
					&&map[cur_x + dx[j]][cur_y + dy[j]] == HOME)		//범위안에 있고 집이 있으면
					home_count++;		//홈카운트증가
				cur_x += dx[j];		//해당좌표 넣어줌
				cur_y += dy[j];		//해당좌표넣어줌
			}
		}
	}
	int profit = home_count*M - price[k];
	if (profit >= 0)		//손해를 안본다면
		Answer = max(Answer, home_count);		//집숫자 비교해서 저장
}

int main()
{
	//freopen("sample_input.txt", "r", stdin);
	int T;
	cin >> T;
	price[1] = 1;
	for (int i = 2; i < 22; i++)
		price[i] = price[i - 1] + 4 * (i - 1);		//운영비용저장
	
	for (int test_case = 1; test_case <= T; test_case++) {
		Answer = -987654321;
		cin >> N >> M;
		Init_map();
		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++)
				for (int k = 1; k <= N + 1; k++) {
					home_count = 0;		//집 카운트 0으로 초기화
					solve(i, j, k);		//solve함수호출
				}
		

		cout << "#" << test_case << " " << Answer << endl;
	}


	return 0;
}