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

출처

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

 

1. 마름모를 탐색하는 방법 찾기

- 아이디어는 K에 따라서 가장 꼭지점의 좌표를 구할 수 있고 가장 위 꼭지점으로 부터 오른쪽 아래 왼쪽 아래

가장 아래 꼭지점으로 부터 오른쪽 위 왼쪽 위로 탐색하도록 함.

 

2. 탐색의 종료 시점 정하기

K에 따른 운영비용이 자신의 비용보다 작다고 바로 종료하면 안됨 더 넓은 영역에서는 참이 될수도 있기 때문에

다른 종료시점을 정해야 하는데

처음에는 모든 인원을 다 카운트 한 경우에 종료 하도록 했는데 하나의 좌표에서 시간이 너무 오래 걸림

따라서 어떤 좌표에서 어떤 K값에 도달했을 때 모든 사람이 다 들어가 있어도 해당 K로부터 이득을 받지 못한다면 종료 하도록 함.

 

3. 실수 수정

마름모 탐색시에 꼭지점에 대한 처리는 for문에서 할 시에 중복이 되므로 따로 해주고 for문에서는 내부 영역만 해주기 때문에 당연히 0보다 큰 경우라고 생각 했으나 마름모다 많이 커진다면 0에 걸친 좌표가 꼭지점이 아닐수도 있으므로

0 이상으로 바꿔 줘야 했다.

 

 

 

 

 

 

#include<iostream>
#include<string.h>
using namespace std;


int arr[20][20];
int person;

int maxa;


int main(void)
{
	
	
	int test_case;
	cin >> test_case;
	
	
	for(int tc =1; tc<= test_case; tc++)
	{
		
		int N,M;
		maxa = 0;
	
		cin >> N >> M;
	
		
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < N; j++)
			{
				cin >> arr[i][j];
				if(arr[i][j])
				person++;
			}
		}
		
		
		for(int i = 0; i <N; i++)
		{
			for(int j=0; j <N; j++)
			{
				int count = 0;
				
				
				if(arr[i][j])
				{
					
					if(maxa < 1)
					{
						maxa = 1;
					}
					count = 1;
					
					
				}
				else
				{
					count = 0;
				}
				
				
				int	K = 2;
				
					
					
					while(1)
					{
						int num = K*K+(K-1)*(K-1);
						
						if(num > person*M )
						{
						
							break; 
						}
						
							if(i+(K-1) < N)
							{
								
							
							if(arr[i+(K-1)][j])
							{
								count++;
								
							}
							}
							
							if(i-(K-1)>=0)
							{
							
							if(arr[i-(K-1)][j])
							{
							
								count++;
							
							}
							}
							
						
						for(int x = K-2; x > 0; x--)
						{
							
							
							if(i-x >=0 && j-x+(K-1) < N)
							{
							
							if(arr[i-x][j-x+(K-1)])
							{
							
								count++;
								
							}
							}
							
							
							if(i-x >= 0 && j+x-(K-1) >=0)
							{
							
							
							if(arr[i-x][j+x-(K-1)])
							{
							
								count++;
							}
							
							}
							
							if(i+x < N && j-x+(K-1) < N)
							{
								
							
							if(arr[i+x][j-x+(K-1)])
							{
							
								
								count++;
								
							}
							}
							
							if(i+x < N && j+x-(K-1) >=0)
							{
							
							if(arr[i+x][j+x-(K-1)])
							{
								
								count++;
							}
							}
							
							
						}
							
							if(j+(K-1) < N)
							{
							
							if(arr[i][j+(K-1)])
							{
								
							
								count++;
								
							}
							}
							
							if(j-(K-1)>=0)
							{
							
							if(arr[i][j-(K-1)])
							{
								
							
							
								count++;
							}
							
							}
						
						
						if(count*M - num < 0)
						{
							
							
							K++;
						}
						else
						{
							
							if(maxa < count)
							{
							
								maxa = count;
							
							}
							K++;
						}
						
					
						
					}
					
					
				
				
				
				
			}
		}
		
		
		
		cout << "#"<<tc <<" "<<maxa<<endl;
		
		
		
		
		
		
		
	}
	
	
	return 0;
	
}