17136 색종이 붙이기

https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

문제 풀이의 접근은 다음과 같이 진행하였다.

각 색종이의 size(1~5)를 5장씩 사용해보며 종이의 1의 갯수가 모두 사라지면 다 붙였다고 판단하고

그때 붙인 색종이의 갯수가 최소값을 구하여 출력하였다.

 

먼저 문제의 조건에서

1. 종이가 0인 부분이 붙이면 안된다.

2. 덮어쓰기가 불가능하다.

3. 붙이려는 색종이가 10x10의 종이 사이즈를 초과하면 안된다.

 

조건 1을 검사하기 위해 check배열을 이용하여 종이가 붙인곳은 true, 붙여지지 않은 곳은 false로 구분.

 

조건 2의 덮어 쓰기의 방지는 check에 붙이려는 1의 x,y좌표에 true값이 있는지 검사를 하고.

3. 붙이려는 정사각형 색종이의 범위가 10,10 을 넘어가는지 검사하였다.

 

해당 사이즈 별로 붙여보는 방식을 사이즈 1~5까지 반복문과 재귀를 이용하여 선택하고.

사용된 사이즈별로 종이 갯수를 검사하기위해 num_counts 라는 배열에서 사용될때마다 종이를 감산 시켜주었다.

 

또한 붙일 수 있는 경우의 수를 파악하기 위해 현재 상태를 백트래킹하여 붙이지 않았을때를 고려해주었다.

 

num_counts[idx] idx는 종이 사이즈를 나타낸다.

update_paper(bool ON_OFF, int x, int y, int paper_size) ON_OFF를 이용하여

x, y의 좌표에서 papersize만큼 종이를 붙이거나 뗀다.

 

종이가 다 붙여졌는지 판단하는 one_count 전역 변수 one_count는 초기에 빈 종이에 1이 몇개 쓰여져 있는지 검사 해당 사이즈만큼 종이를 붙였다면 +- (paper_size의 제곱) 값을 이용하여 수를 갱신 시켜준다.

 

#include<iostream>
#include<vector>
using namespace std;

bool Is_stick_paper(int paper_size,int x,int);
void go(int x, int y, int attached_cnt);
void update_paper(bool ON_OFF, int x, int y, int paper_size);

int arr[10][10];
int check[10][10]; //
int num_counts[7] = { 0,5,5,5,5,5,0 }; //사이즈별 남은 종이 갯수

int one_count; //종이에 1의 갯수
int min_ans = 1e9;

bool isAble_Stick = false;
int main(void)
{
	for (int i = 0; i < 10; ++i)
	{
		for (int j = 0; j < 10; ++j)
		{
			cin >> arr[i][j];
			if (arr[i][j])
			{
				one_count += 1;
			}
		}
	}
	if (one_count == 0)
	{
		cout << 0 << '\n';
		return 0;
	}
	

	go(0,0,0);
	if (isAble_Stick) //모두 붙이는것이 가능한지
	{
		cout << min_ans << '\n';
	}
	else cout << -1 << '\n'; //아니라면 -1 출력
	
	return 0;
}
void go(int x,int y, int attached_cnt)
{
	if (one_count == 0) //다 붙인 경우 one_count는 초기 1의 갯수
	{
		isAble_Stick = true;
		if (min_ans > attached_cnt)
			min_ans = attached_cnt;
		return;
	}
	
	int xn = 0, yn = 0; //다음 부착을 시도해볼 xn, yn 좌표
	
	//다음 부착해야할 곳을 찾는중.
	for (int i = 0; i < 10; ++i)
	{
		bool isout = false;
		for (int j = 0; j < 10; ++j)
		{
			if (arr[i][j] == 1 && check[i][j]==false) //1이여서 붙여아하고, 겹치지 않는곳.
			{
				xn = i;
				yn = j;
				isout = true;
				break;
			}
		}
		if (isout) break;
	}

	// 1~5사이즈까지 붙여봄
	for (int paper_size = 1; paper_size <=5; paper_size++)
	{
		if (Is_stick_paper(paper_size, xn, yn)) //해당 사이즈의 종이를 xn,yn에 붙일 수 있는지
		{
			num_counts[paper_size] -= 1; // 사이즈별 남은 종이 갯수 [0,5,5,5,5,5,0]
			update_paper(true, xn, yn, paper_size); // check배열에 true로 색종이 붙이기.
			one_count -= (paper_size*paper_size); // one_count ==0 : 모두 붙인경우

			go(xn, yn, attached_cnt + 1);

			num_counts[paper_size] += 1; //롤백
			update_paper(false, xn, yn, paper_size);  //롤백
			one_count += (paper_size*paper_size); //떼어낸 갯수만큼 롤백

		}
		
	}
	return;
}
void update_paper(bool ON_OFF, int x, int y, int paper_size)
{
	for (int i = 0; i < paper_size; ++i)
	{
		for (int j = 0; j < paper_size; ++j)
		{
			check[x+i][y+j] = ON_OFF;
		}
	}
}
bool Is_stick_paper(int paper_size,int x,int y)
{
	if (num_counts[paper_size] == 0) return false; //해당 사이즈의 종이가 모자란경우
	if (x + paper_size > 10 || y + paper_size > 10) return false; //붙이는 스티커 사이즈가 종이 사이즈를 넘어가는경우
	int xn = x;
	int yn = y;

	for (int i = 0; i < paper_size; ++i)
	{
		for (int j = 0; j < paper_size; ++j)
		{
			if (arr[x+i][y+j] == 0) return false; // 1이 칠해져 있지 않은곳.
			if (check[x+i][y+j] == true) return false; //스티커가 겹칠때
		}
			
	}

	return true;
}