고양멍멍이

[문제링크]

0. 큰 색종이부터 차례대로, 모든 붙일수 있는 부분에 붙여보고 떼어보며 진행하는 brute-force 문제

chk함수 : n*n 공간이 전부 1이면, 색종이를 붙일 수 있으면 true를 반환

remove : n*n 색종이를 붙이는 함수, 모든 1을 0으로 전환

repair : n*n 색종이를 떼는 함수, 모든 0을 1로 전환

1. 10*10 색종이의 모든 가능한 n*n 공간을 검사하며 색종이를 붙여보고, 더이상 붙일 수 없다면 n-1번째 색종이로 넘어가서 붙여보기를 시도한다.

2. 가지치기 1 : 앞으로 사용 가능한 모든 색종이를 사용해도 현재 남아있는 1의 갯수를 다 덮을만큼 충분하지 않다면, 포기하고 돌아간다.

3. 가지치기 2 : 이전 연산에서 구했던 해답보다 더 많은 색종이를 이미 사용했다면, 포기하고 돌아간다

4. min은 최대 25이므로, 그 이상의 값을 초깃값으로 지정한 후 갱신되지 않았다면 -1을 출력, 아니면 갱신된 값을 출력한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		map=new int[10][10];
		int num=0;
		for (int i = 0; i < 10; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < 10; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				if(map[i][j]==1)num++;
			}
		}
		
		min=Integer.MAX_VALUE;
		search(0,0,0,5, num);
		System.out.println(min==Integer.MAX_VALUE?-1:min);
	}
	static int min;
	static int[][]map;
	static int limit[]=new int[] {0,5,5,5,5,5};
	static int[] maximunArea= {0,0,5,20,45,80};
	
	static void search(int x, int y, int cnt, int k, int num) {
    
		//가지치기
		//앞으로 쓸수잇는 모든 색종이를 다 써도 모든 1을 덮을수 없다면, 돌아간다
		if(maximunArea[k]+k*k*limit[k] < num) {
			return;
		}
		//다른 정답에서 구한 min값보다 이미 많은 수의 색종이를 썼다면, 돌아간다
		if(cnt>=min)return;
		//1을 다 붙였으면 min 갱신 후, 돌아간다
		if(num==0) {
			min=min<cnt?min:cnt;
			return;
		}
		//다 붙이는데 실패했다면, 돌아간다.
		if(k==0)return;
		
        
		
		for (int i = x; i < 11-k; i++) {
			for (int j = 0; j < 11-k; j++) {
				if(map[i][j]==1 && limit[k]>0) {
					if(chk(i,j,k)) {
						//제거
						remove(i,j,k);
						limit[k]--;
						//그 위치부터 다시 재귀
						
						search(i,j,cnt+1,k, num-k*k);
						
						//복구
						repair(i,j,k);
						limit[k]++;
					}
				}
			}
		}
		
		
		search(0,0,cnt,k-1, num);
		
	}
	
	static boolean chk(int x, int y, int k) {
		for (int i = x; i < x+k; i++) {
			for (int j = y; j < y+k; j++) {
				if(map[i][j]==0)return false;
			}
		}
		return true;
	}
	static void remove(int x, int y, int k) {
		for (int i = x; i < x+k; i++) {
			for (int j = y; j < y+k; j++) {
				map[i][j]=0;
			}
		}
	}
	static void repair(int x, int y, int k) {
		for (int i = x; i < x+k; i++) {
			for (int j = y; j < y+k; j++) {
				map[i][j]=1;
			}
		}
	}
	
}

[문제링크]

0. 최대 무게 500g인 추가 최대 30개 들어오므로, 최대 탐색 가능 범위는 -15000 ~ 15000

1. 추를 올리지 않는 경우, 물건의 반대편에 올리는 경우(+), 물건쪽에 올리는 경우(-) 3가지 경우를

모든 추에 대해 재귀로 진행하며, 이 과정에서 거치는 모든 무게를 true로 표시한다.

  - 이때, 추를 추가한 무게가 앞 재귀에서 나왔던 무게일 경우, 중복 연산이 발생하므로 진입하지 않는다 (가지치기) 

2. 물건의 무게를 입력받고, 15000초과의 무게일 경우 즉시 N을, 그 이하일 경우 true/false 값에 따라 Y/N을 출력해준다.

추가적으로 생각해본 개선점

1. dfs처럼 재귀를 돌며 깊은 단계에 진입 때문에, 깊은 단계에서 possible 배열이 수정되어도

  얕은 단계에 영향을 주지 못하도록 possible배열이 2중으로 구현되어야 했음.

  - bfs처럼 큐에 넣어가며 단계별로 작업했다면 possible 배열 하나로 가능하지 않았을까?

2. -7500 값은 적어도 500g추 15개가 있어야 도달 가능한 값이므로,

  나머지 추 15개를 전부 +로 설정해도 0이상의 값을 가질 수 없다.

  - -7500 ~ 15000으로 possible 배열을 사용하면 크기를 25%정도 절약할 수 있었음.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int num;
	static int[] weight;
	static boolean[][] possible;
    
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		
		num=Integer.parseInt(br.readLine());
		weight = new int[num];
		
		//추 무게 입력
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < num; i++) {
			weight[i]=Integer.parseInt(st.nextToken());
		}
		
		//해당무게의 표현 가능 여부 표시를 위한 boolean배열
		//추는 500g이하, 30개이하이므로, 최대 +15000, 최소 -15000까지 탐색할 수 있다
		//15000 지점을 가상의 0으로 가정, 30001개의 배열로 선언한다.
		possible = new boolean[30001][num];
		
		//추에 대한 선택지는 3가지 - 올리지 않는다|구슬쪽에 올린다|반대편에 올린다
		//3가지 선택지를 탐색하며 모든 계산 가능한 경우를 true로 마크한다
		search(0, 15000);//초깃값은 가상의 0인 15000

		//구슬의 개수 입력받기
		int ball_num = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < ball_num; i++) {
			int ball_weight = Integer.parseInt(st.nextToken());
			//최대 무게인 15000을 넘으면 바로 N
			if(ball_weight>15000) {
				sb.append("N ");
			}
			//해당 무게가 가능하다면 Y, 아니면 N을 기록한다.
			else sb.append(possible[ball_weight+15000][num-1]?"Y ":"N ");
		}
		System.out.println(sb);
	}
    
	static void search(int cnt, int cur) {
		//모든 추에 대해 탐색 종료
		if(cnt==num) {
			return;
		}
		else {
			//해당 무게에 도달한 적 없다면 진입한다
			if(!possible[ cur+weight[cnt] ][cnt]) {
				possible[ cur+weight[cnt] ][cnt]=true;
				search(cnt+1, cur+weight[cnt]);
			}
			//해당 무게에 도달한 적 없다면 진입한다
			if(!possible[ cur-weight[cnt] ][cnt]) {
				possible[ cur-weight[cnt] ][cnt]=true;
				search(cnt+1, cur-weight[cnt]);
			}
			//올리지 않는다
			possible[cur][cnt]=true;
			search(cnt+1, cur);
		}
	}
}