논리훈련문제,

논리문제는 아이디어를 내기까지가 상당히 까다롭다.

결국 많은 경험이 필요하다. 다음 문제를 보자

 

문제

N*N의 영역이 주어진다.(N : 2~10000)

해당 영역에 먼지가 떨어져 있다.

청소를 단 한번 할 수 있다. 청소 구역의 둘레 길이 L(4~100이며 짝수이다)이 주어진다.

먼지의 개수는 M(1~100)으로 주어지며 먼지의 X,Y좌표값이 주어진다.

주어진 L의 조건에서 청소 시 가장 많이 제거할 수 있는 먼지의 갯수를 구하라

 

입력

6 10 6

2 2

4 6

5 2

6 4

2 4

3 3

 

출력

4

---

접근방법

주어진 케이스는 아래와 같다.

청소영역 둘레가 10이라 청소영역 가로세로 2*3 조합도 가능하고 1*4 조합도 가능하다. 아이디어를 생각해본다.

1) 간단하게 N을 기준으로 모든 영역을 수행한다.

N을 기준으로 수행할 시 N이 최대 10000이기 때문에 10000*10000을 탐색해야하는데 시간복잡도가 매우 높아진다.

 

2) 먼지 하나를 기준점으로 좌우상하 실시한다.

먼지 하나를 기준으로 할 시 가능해보인다. 단, 먼지가 반드시 꼭지점에 위치해야하므로 먼지가 꼭지점에 없는 경우에는 정답을 도출 할 수 없다.

 

3) 기준점을 먼지하나로 하지말고 모든 먼지끼리 조합을 하면 되지 않을까?

먼지의 갯수는 100개 이므로 100*100의 기준점이 있으며 / L이 최대 100이므로 청소구역의 경우의 수는 49가지이다.

또한 먼지를 탐색하는 총먼지의 개수는 최대 100이므로

따라서 총 경우의 수는 49 * 100 * 100 * 100이 되겠다.

즉,

a. 49가지의 가로 세로를 구하여

b. 각 먼지 좌표별로 기준점을 구해서

c. 가로 세로 안에 먼지가 들어있는지 count하면 된다.

 

 

#include <stdio.h>

int y[110];
int x[110];
int N;
int L;
int M;   //
int sol;

void Input(){
	scanf("%d %d %d", &N, &L, &M);
	for(int i=1; i<=M; i++){
		scanf("%d %d", &x[i], &y[i]);
	}
}

int Count(int x1, int y1, int x2, int y2){
	int cnt=0;
	for(int i=1; i<=M; i++){
		if(x1 <= x[i] && x[i] <=x2 && y1 <= y[i] && y[i] <= y2 ){
			cnt++;
		}
	}
	return cnt;
}

int Solve(){
	int w;
	int h;
	int k = L/2; //L은 짝수
	int ans = -1;
	int cnt = -1;
	
	for(h=1; h<k; h++){ // 높이 1~49
		w=k-h; // h 1일때
		for(int r=1; r<=M; r++){
			for(int c=1; c<=M; c++){ //좌표의 x,y별로 다 수행
				cnt = Count(x[r],y[c],x[r]+h,y[c]+w);
				if(ans < cnt) ans = cnt;
			}
		}
	}
	return ans;
}


int main() {
	Input();
	printf("%d", Solve());
	//주어진 X,Y 좌표로만 경우의 수를 판단하면 모든 경우를 파악할 수 없음
	//주어진 X,Y의 X와 Y각각의 경우에 대해서 판단해야함 
	
	return 0;
}