[BOJ] 17136. 색종이 붙이기

import java.util.Scanner;

public class Main {
	static Scanner sc=new Scanner(System.in);
	static int map[][];
	static int cnt[]={0,5,5,5,5,5};
	static int N;
	static boolean flag;
	static int min=Integer.MAX_VALUE;
	public static void main(String[] args) {
		N=10;
		map=new int [N][N];
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j]=sc.nextInt();
				if(!flag && map[i][j]==1) {
					flag=true;
				}
			}
		}
		
		if(!flag) System.out.println(0);
		else {
			go(0,0);
			if(min!=Integer.MAX_VALUE) {
				System.out.println(min);
			}else {
				System.out.println(-1);
			}
		}
	}
	
	
	public static void go(int x,int y) {
		if(x==N && y==0) {
			int sum=25;
			for (int i = 1; i < cnt.length; i++) {
				sum-=cnt[i];
			}
			if(sum!=0 && sum<min) {
				min=sum;
			}
		}
		if(x < 0 || x > N-1 || y < 0 || y > N-1) return;	
		
		int nx,ny;
		
		if(y<N-1) {
			nx=x; ny=y+1;
		}else {
			nx=x+1; ny=0;
		}
		if(map[x][y]==0) go(nx,ny);
		for (int i = 5; i >= 1; i--) {
			if(!check(x,y,i)) continue;
			if(cnt[i]>0) {
				fill(x,y,i,0);
				cnt[i]--;
				go(nx,ny);
				cnt[i]++;
				fill(x,y,i,1);
			}
		}
	}
	
	public static void fill(int x,int y,int num,int zeroOne) {		
		if(x+num>10 || y+num>10) return;
		
		for (int i = x; i < x+num; i++) {
			for (int j = y; j < y+num; j++) {
				map[i][j]=zeroOne;
			}
		}
	}
	
	public static boolean check(int x,int y, int num) {
		if(x+num>10 || y+num>10) return false;
		
		for (int i = x; i < x+num; i++) {
			for (int j = y; j < y+num; j++) {
				if(map[i][j]==0) {
					return false;
				}
			}
		}
		return true;
	}
}

import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int map[][] = new int[10][10];
	static int cnt[] = { 0, 5, 5, 5, 5, 5 };
	static int ans=Integer.MAX_VALUE;
	public static void main(String[] args) {
		int sum = 0;
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		int x=next(0,0).x;
		int y=next(0,0).y;
		
		go(x,y);

		if (ans==Integer.MAX_VALUE)
			System.out.println("-1");
		else
			System.out.println(ans);

	}

	public static Point next(int x,int y) {
		boolean flag=false;
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				if (map[i][j] == 1) {
					flag=true;
					y=j;
					break;
				}
			}
			if(flag) {
				x=i;
				break;
			}
		}
		if(flag==false) {
			return new Point(10,10);
		}else {
			return new Point(x,y);
		}
	}

	public static void fillZero(int x, int y, int s) {
		if(x+s>10 || y+s>10) return;
		for (int i = 0; i < s; i++) {
			for (int j = 0; j < s; j++) {
				map[x + i][y + j] = 0;
			}
		}
	}

	public static void fillOne(int x, int y, int s) {
		if(x+s>10 || y+s>10) return;
		for (int i = 0; i < s; i++) {
			for (int j = 0; j < s; j++) {
				map[x + i][y + j] = 1;
			}
		}
	}
	
	public static boolean check(int x,int y,int s) {
		if(x+s>10 || y+s>10) return false;
		boolean flag=true;
		for (int i = 0; i < s; i++) {
			for (int j = 0; j < s; j++) {
				if(map[x+i][y+j]==0) {
					flag=false;
					break;
				}
			}
		}
		return flag;
	}
	
	
	public static void go(int x,int y) {
		for (int i = 1; i < cnt.length; i++) {
			if(cnt[i]<0) {
				return;
			}
		}
		if(x==10 && y==10) {
			int count=25;
			for (int i = 1; i < cnt.length; i++) {
				count-=cnt[i];
			}
			if(ans>count) {
				ans=count;
			}
			return;
		}
		for (int size = 5; size >= 1 ; size--) {
			if(check(x,y,size)==false) continue;
			fillZero(x,y,size);
			cnt[size]--;
			go(next(x,y).x,next(x,y).y);
			fillOne(x,y,size);
			cnt[size]++;
		}
		
	}
	
	public static class Point {
		int x, y;
		Point(int x,int y){
			this.x=x;
			this.y=y;
		}
	}
}